单调栈的模板题吧 没啥好讲的 被卡了一点空间 去掉了一个数组就过了
参考洛谷 理想的正方形
#include <bits/stdc++.h>
using namespace std;
const int N = 5002;
int n,m,k,FRONT,BACK;
int Q[N];
int X[N][N];
int a[N][N];
typedef long long ll;
int main(){scanf("%d%d%d",&n,&m,&k);for (int I=1;I<=n;I++)for (int i=1;i<=m;i++){a[I][i]=I*i/__gcd(I,i);}for (int I=1;I<=n;I++){FRONT=BACK=1;Q[1]=0;for (int i=1;i<=m;i++){while (a[I][i]>=a[I][Q[BACK]]&&FRONT<=BACK) BACK--;BACK++;Q[BACK]=i;while (i-Q[FRONT]>=k) FRONT++;if (i>=k) X[I][i-k+1]=a[I][Q[FRONT]];}}for (int I=1;I<=m-k+1;I++){FRONT=BACK=1;Q[1]=0;for (int i=1;i<=n;i++){while (X[i][I]>=X[Q[BACK]][I]&&FRONT<=BACK) BACK--;BACK++;Q[BACK]=i;while (i-Q[FRONT]>=k) FRONT++;if (i>=k) a[i-k+1][I]=X[Q[FRONT]][I];}}ll ans = 0;for (int I=1;I<=n-k+1;I++)for (int i=1;i<=m-k+1;i++)ans+=a[I][i];printf("%lld\n",ans);return 0;
}