Fake Maxpooling

Fake Maxpooling

Problem:

给出一个\(n \times m\)的矩阵和一个整数\(k\)，对于矩阵中每个位置\(A_{i,j}=lcm(i,j)\),\(i\)和\(j\)的最小公倍数。请你计算除所有\(k*k\)大小的子矩阵的最大值并将所有最大值求和。

Input：

只有一行包含整数\(n,m,k(1\leq n,m \leq 5000,1\leq k \leq min(n,m)\)

Output:

只有一行，输出最大值之和

Example：

input

3 4 2

output

38

note

The given matrix is:
1 2 3 4
2 2 6 4
3 6 3 12
The maximums among all \(2\times 2\) submatrices are \(2,6,6,6,6,12\) respectively, and their sum is 38.

Solution:

两遍单调队列处理出矩阵中每个子矩阵的最大值，遍历一遍求和。

关于单调队列：

参考大神：https://www.cnblogs.com/RealMadrid/articles/10599588.html

Code:

/**********************************************************
* @Author:             Kirito
* @Date:               2020-07-18 16:33:16
* @Last Modified by:   Kirito
* @Last Modified time: 2020-07-18 17:17:05
* @Remark: 
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=5111;
int n,m,k;
int mart[maxn][maxn];
ll sum[maxn][maxn];
deque<int> box;

int gcd(int x,int y){
    return x%y==0?y:gcd(y,x%y);
}

int lcm(int x,int y){
    return x*y/gcd(x,y);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif
    FAST;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mart[i][j]=lcm(i,j);
        }
    }
    //first round 
    for(int i=1;i<=n;i++){
        while(!box.empty()) box.pop_front();
        for(int j=1;j<=m;j++){
            box.push_back(mart[i][j]);
            while(!box.empty()&&box.front()<mart[i][j])
                box.pop_front();
            if(box.size()>k){
                box.pop_front();
                while(!box.empty()&&box.front()<mart[i][j])
                    box.pop_front();
            }
            mart[i][j]=box.front();
        }
    }
    //second round
    for(int j=1;j<=m;j++){
        while(!box.empty()) box.pop_front();
        for(int i=1;i<=n;i++){
            box.push_back(mart[i][j]);
            while(!box.empty()&&box.front()<mart[i][j])
                box.pop_front();
            if(box.size()>k){
                box.pop_front();
                while(!box.empty()&&box.front()<mart[i][j])
                    box.pop_front();
            }
            mart[i][j]=box.front();
        }
    }
    ll ans=0;
    for(int i=k;i<=n;i++){
        for(int j=k;j<=m;j++)
            ans+=mart[i][j];
    }
    cout<<ans<<endl;
    return 0;
}