Fake Maxpooling

Fake Maxpooling

Problem:

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

Input：

只有一行包含整数(n,m,k(1leq n,m leq 5000,1leq 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 imes 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;
}