牛客多校第二场 F-Fake Maxpooling（单调队列）

题意

一个 n*m 的矩阵 A_i,j=lcm(i,j) (i与j的最小公倍数) ，求其所有k阶子矩阵的最大值之和

• 范围： 1≤n,m≤5000 1<=k<=min{n,m}
• 链接： Fake Maxpooling
• 输入

3 4 2

• 输出

38

解题思路

• 用gcd打表（据说没优化会超时，可能是数据水）
• 用单调队列分别维护行和列

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m,k,a[5001][5001],b[5001][5001],l,r,dl[5001];
ll ans;
ll gcd(ll a,ll b)
{if(a%b==0)return b;else return gcd(b,a%b); 
}
ll lcm(ll a,ll b)
{return a*b/gcd(a,b);
}
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!a[i][j]){a[i][j]=lcm(i,j);a[j][i]=a[i][j];}//单调队列先维护每一行的长度为k的区间的最大值 并记录下来for(int i=1;i<=n;i++){l=1;r=0;for(int j=1;j<=m;j++){while(l<=r&&a[i][j]>=a[i][dl[r]]) r--;dl[++r]=j;while(l<=r&&dl[l]<=j-k) l++;if(j>=k) b[i][j]=a[i][dl[l]];}}//在对上面记录的数组维护列的最大值for(int j=k;j<=m;j++){l=1;r=0;for(int i=1;i<=n;i++){while(l<=r&&b[i][j]>=b[dl[r]][j]) r--;dl[++r]=i;while(l<=r&&dl[l]<=i-k) l++;if(i>=k) ans+=b[dl[l]][j];}}printf("%lld",ans);return 0;
}