一直想写牛客的题解，一直拖就拖到了现在，果然有想法就要立马去做，不然就和我一样了
D题就不写了，简单的减法判断，我写一下F题
题目链接
题意大概就是有这样一个 n * m 的矩阵a，矩阵的每一项 a[i][j] = lcm(i,j) ，然后每次求一个 k * k 的子矩阵中的最大值，将这些最大值求和
题目其实不难理解，但是写起来就没那么容易了
我们知道每次划分一个 k * k 的子矩阵求最大值很麻烦，那我们可以去分别求行和列的最大值并储存下来
然后我们就想到了前几天刚刚接触的单调队列
首先枚举 n * m 的矩阵，我们可以在构造单调队列的同时计算矩阵的每一项，之前内存超限就卡在这里，卡了将近一个小时，还以为是单调队列的思路写出来的代码有问题
构造一个递减的单调队列，这样队列的首项就是最大值
第一次循环我们就可以求出 m - k + 1 列的最大值（子矩阵的列数是k，在大矩阵中可以得到 m - k + 1 次最大值）
然后去枚举这 m - k + 1 列 n 行，构造一个递减的单调队列
这时符合 j >= k 时答案就找到了，求和即可
struct Node{int val , pos;
};
Node que[5001];
int n,m,k,Max[5001][5001];int main(){io >> n >> m >> k;for(int i=1;i<=n;i++){int head = 1 , tail = 0;for(int j=1;j<=m;j++){int now = i / gcd(i , j) * j;while(head <= tail && now >= que[tail].val) tail--;que[++tail].val = now; que[tail].pos = j;if(head <= tail && j - que[head].pos + 1 > k) head++;if(j >= k){Max[i][j-k+1] = que[head].val;}}}ll ans = 0;for(int i=1;i<=m-k+1;i++){int head = 1 , tail = 0;for(int j=1;j<=n;j++){int now = Max[j][i];while(head <= tail && now >= que[tail].val) tail --;que[++tail].val = now; que[tail].pos = j;if(head <= tail && j - que[head].pos + 1 > k) head++;if(j >= k){ans += que[head].val;}}}printf("%lld\n",ans);return 0;
}