Fake Maxpooling

链接：https://ac.nowcoder.com/acm/contest/5667/F
来源：牛客网

题目描述:

Given a matrix of size n×m and an integer k, where Ai,j=lcm(i,j), the least common multiple of i and j. You should determine the sum of the maximums among all k×k submatrices.

输入描述：

Only one line containing three integers n,m,k (1≤n,m≤5000,1≤k≤min{n,m}).

输出描述：

Only one line containing one integer, denoting the answer.

solution：

矩阵第i行，j列的值是i和j的最小公倍数
我们通过对每一行的每k个数记录其最大值，然后对于每列的每k个数进行记录最大值。每次O(1)找出当前k个数的最大值，我们可以采用deque，deque中存的是数据的位置，把比当前小的数都pop掉，然后再将当前的数的位置加上，判断deque中第一个位置的管辖范围是否超出，超出也pop掉，然后每超出的第一个数就是k个数内的最大值，列的处理也相同

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int tu[5005][5005];
int d[5005][5005];
ll ans=0;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            tu[i][j]=lcm(i,j);
    deque<int> q;
    for(int i=1;i<=n;i++)
    {
        while(!q.empty())
            q.pop_front();
        for(int j=1;j<=m;j++)
        {
            while(!q.empty()&&tu[i][q.back()]<tu[i][j])
                q.pop_back();
            q.push_back(j);
            while(q.front()+k-1<j)
                q.pop_front();
            d[i][j]=tu[i][q.front()];
        }
    }
    for(int j=k;j<=m;j++)
    {
        while(!q.empty())
            q.pop_back();
        for(int i=1;i<=n;i++)
        {
            while(!q.empty()&&d[q.back()][j]<d[i][j])
                q.pop_back();
            q.push_back(i);
            while(q.front()+k-1<i)
                q.pop_front();
            if(i>=k)
            ans+=d[q.front()][j];
        }
    }
    cout<<ans;
}