F-Fake Maxpooling

题目大意

给你三个数 $n$ $m$ $k$ ，让你求出这 $n*m$ 的矩阵各个大小为 $k*k$ 的方阵中最大值的总和是多少，矩阵中 $a_{i,j}=i*j/gcd(i,j)$ ；

解题思路

这道题可以有多种解法，~~然而比赛的时候我一个没想起来，~~，后来看到好多大佬说可以用单调队列去解，然后看了看大佬们的博客总算是知道怎么搞了，
我们可以单调队列先处理每行连 $k$ 个数的最大值，然后开始向后滑动，这里最巧妙的是单调队列中存的是这连续 $k$ 个数字的下标，这样既方便滑动也不影响记录最大值，我们根据单调队列的性质将这个矩阵按照行先滑动一遍并且每操作一格记录这个位置的最大值后，比如说 $b_{i,j}$ 就表示 $a_{i,j-k_1}$ 到 $a_{i,j}$ 这连续 $k$ 个数中的最大值。
既然行我们处理完了，那我们就用刚才处理好的数组 $b$ 来按列处理这样就可以得到大小为 $k*k$ 方阵中的最大值了。不理解的可以画个图自己模拟一遍。

代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fast ios::sync_with_stdio(0)
const int mx=5600;
int q[10000];// 数字模拟队列 
int a[mx][mx];
int b[mx][mx];//处理每行连续k个数字中最大值 
int st,en;// st表示 前面的 en后面 
int n,m,k;
int gcd(int a,int b) {return b?gcd(b,a%b):a;}

int main()
{
    fast;
    ll ans=0;
    cin>>n>>m>>k;
    //构造矩阵 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=i*j/gcd(i,j);
        }
    }

    for(int i=1;i<=n;i++)
    {
        st=en=1;
        q[en++]=0;
    //先处理前 k-1个元素
        for(int j=1;j<k;j++){
            while(st!=en&&a[i][q[st]]<=a[i][j]) st++;
            q[en++]=j;
        }
        for(int j=k;j<=m;j++){
// 因为队列中记录的是下标 所以下标如果不在 j-k+1 到 j这个区间的元素都要弹出 
            while(st!=en&&q[st]<=j-k) st++;
    //这里就是普通的单调队列按照 大的在前面    
            while(st!=en&&a[i][q[en-1]]<=a[i][j]) en--;
            q[en++]=j;
    // 此时的 q[st] 中就是当前连续的 k个值中最大值的下标 
            b[i][j]=a[i][q[st]];
        }
    }
//下面的过程和上面相似，只不过行换成列了    
    for(int j=k;j<=m;j++){
        st=en=1;
        q[en++]=0;
        for(int i=1;i<k;i++){
            while(st!=en&&b[q[st]][j]<=b[i][j]) st++;
            q[en++]=i;
        }
        for(int i=k;i<=n;i++){
            while(st!=en&&q[st]<=i-k) st++;
            while(st!=en&&b[q[en-1]][j]<=b[i][j]) en--;
            q[en++]=i;
//此时的 q[en++] 就是当前这个 k*k的矩阵中的最大值了    
            ans+=b[q[st]][j];
        }
    }
    cout<<ans<<"\n";
    return 0;
 }