Fake Maxpooling（2020多校第二场F）
@[toc]

题意：

一个n * m的矩阵，第i行第j列的值是lcm（i，j），然后给定一个 k * k的子矩阵（k<=min(n,m)），然后求出大矩阵中每个子矩阵的最大值的和
看样例：

3 4 2
38

给的矩阵是：
1 2 3 4
2 2 6 4
3 6 3 12
所有2 * 2的子矩阵的最大值分别是 ：
2,6，6,6，6,12，总和是38

题解：

暴力求法是O（n m log n），先考虑O（n m）的做法

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(!Gcd[i][j])
        for(int k=1;k*i<=n&&k*j<=m;k++)
         Gcd[k*i][k*j]=k,A[k*i][k*j]=i*j*i*k;
    }
}

之后再用单调队列

曾经做过一个叫滑动窗口的题，其实和这个是一个类型，那个是一维的，本题这个是二维的
滑动窗口的题解（含题目链接）
分别求出每行和每列的k个长度区间的最大值
tail表示尾，head表示头，不断得到区间内的最大值，并存进b中，最终覆盖给a
其实就是把二维的拆分成行和列的一维，然后分别进行和滑动窗口那个题一样的操作

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
int a[maxn][maxn];
int b[maxn];
int qu[maxn];
int n,m,k;
int gcd(int a,int b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
void getr(int j)//固定列 
{
    memset(qu,0,sizeof(qu));
    int head=0;
    int tail=1;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&qu[head]+k<=i)head++;
        while(head<=tail&&a[i][j]>a[qu[tail]][j])tail--;
        qu[++tail]=i;
        if(i>=k)
        b[i-k+1]=a[qu[head]][j];    
    }
    for(int i=1;i<=n-k+1;i++)
    a[i][j]=b[i];

}
void getl(int i)//固定行 
{
    memset(qu,0,sizeof(qu));
    int head=0;
    int tail=1;
    for(int j=1;j<=m;j++)
    {
        while(head<=tail&&qu[head]+k<=j)head++;
        while(head<=tail&&a[i][j]>a[i][qu[tail]])tail--;
        qu[++tail]=j;
        if(j>=k)
        b[j-k+1]=a[i][qu[head]];
    }
    for(int j=1;j<=m-k+1;j++)
    a[i][j]=b[j];
}
int main()
{

    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        a[i][j]=lcm(i,j);
    }
    for(int i=1;i<=m;i++)
    getr(i);
    for(int i=1;i<=n;i++)
    getl(i);
    long long  sum=0;
    for(int i=1;i<=n-k+1;i++)
    {
        for(int j=1;j<=m-k+1;j++)
        {
            sum+=a[i][j];
        }
    }
    printf("%lld\n",sum);
}