题目大意

给定整数n,m,k，构造一个n×m的矩阵A，其中Ai,j = lcm(i,j)，第i行j列的数是i和j的最小公倍数。 求所有k×k个子矩阵中的最大值之和。

解题思路

先用尽可能快的操作将整张表求出来，接下来用单调队列。（附上大佬详解链接https://www.cnblogs.com/RealMadrid/articles/10599588.html）
一次横排，一次竖排，记录每个区间中最大值的下标，顺便求和即可（这题要将代码讲的精细太头疼了）
用到双端队列deque，用法与queue相近，且添加了一些更舒服的操作，在头尾都可以删除或添加。（pop_back，pop_front，push_back，push_front等等）

AC代码 

#include<bits/stdc++.h>
using namespace std;
int a[5010][5010],b[5010][5010],n,m,k;
long long ans; //ans用long long避免超限
deque<int> q;
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    int i,j,t;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a[i][j]=i*j/gcd(i,j);
    for(i=1;i<=n;i++)
    {
        t=0;
        while(!q.empty()) q.pop_back();
        for(j=1;j<=k;j++)
        {
            while(q.size() && a[i][q.back()]<=a[i][j]) q.pop_back();
            q.push_back(j);
        }
        t++,b[i][t]=a[i][q.front()];
        for(j=k+1;j<=m;j++)
        {
            while(q.size() && a[i][q.back()]<a[i][j]) q.pop_back();
            q.push_back(j);
            while(q.size() && q.front()<j-k+1) q.pop_front();
            t++,b[i][t]=a[i][q.front()];
        }
    }
    for(i=1;i<=t;i++)
    {
        while(!q.empty()) q.pop_back();
        for(j=1;j<=k;j++)
        {
            while(q.size() && b[q.back()][i]<=b[j][i]) q.pop_back();
            q.push_back(j);
        }
        ans+=b[q.front()][i];
        for(j=k+1;j<=n;j++)
        {
            while(q.size() && b[q.back()][i]<=b[j][i]) q.pop_back();
            q.push_back(j);
            while(q.size() && q.front()<j-k+1) q.pop_front();
            ans+=b[q.front()][i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}