题目描述
看这数据量5000*5000，一般的暴力就不行，于是就想到单调队列
然后打了，在60分的时候报MLE，然后查了好久，把long long改int才过
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int g[5005][5005],Lcm[5005][5005],n,m,i,j,k,l,r,ans;
struct node
{int c,i;
};
int gcd(int x,int y){return y==0? x:gcd(y,x%y);}
int main()
{scanf("%d%d%d",&n,&m,&k);ll ans=0;memset(g,0,sizeof(g));for (i=1;i<=n;i++)//行的单调队列{node b[10005]={0};l=5001;r=5001;for (j=1;j<=m;j++){Lcm[i][j]=i*j/gcd(i,j);while(l!=r && j-b[l-1].i>=k) l--;while(l!=r && b[r].c<Lcm[i][j]) r++;r--;b[r].i=j;b[r].c=Lcm[i][j];g[i][j]=b[l-1].c;}}for (j=1;j<=m;j++)//列的单调队列{node b[10005]={0};l=5001;r=5001;for (i=1;i<=n;i++){while(l!=r && i-b[l-1].i>=k) l--;while(l!=r && b[r].c<g[i][j]) r++;r--;b[r].i=i;b[r].c=g[i][j];if (i>=k && j>=k) ans+=b[l-1].c;}}printf("%lld\n",ans);
}