双端单调队列

题目来源：https://ac.nowcoder.com/acm/contest/5667/F

题意：给定一个n* m的矩阵A，A(i,j)=lcm(i,j)（最小公倍数），求所有A中的所有k* k的子矩阵中元素最大值之和。

做题历程：很不巧，这题也不是我负责，但队友过了，可不是那么轻松，而且此题也蕴涵着很多知识点，我不是很了解，所以还是拿来分析分析。

解题思路：如果直接按照思路来，把这个矩阵用二维数组整出来，然后再一一求子矩阵，再求子矩阵中的最大值，那时间肯定会爆掉。所以得用上巧妙的方法来解这一题。在这里我学习了一下，要用上单调队列来进行预处理（什么是单调队列，手推见上图），类似于滑动窗口，要对矩阵进行压缩预处理，进而求结果。

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

typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
#define N 5010
int g[N][N];
int max1[N][N];

struct Node        //定义一个val，id
{
    int val,id;
    Node(int val,int id):val(val),id(id){}
};

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!g[i][j])
            {
                    for(int k=1;k*i<=n&&k*j<=m;k++)
                {
                    g[k*i][k*j]=k;
                    max1[k*i][k*j]=i*j*k;//矩阵表示出来。 
                }         
            }


    for(int i=1;i<=n;i++)                            //先进行预处理 
    {
        deque<Node>q;
        for(int j=1;j<=k-1;j++)
        {
            while(q.size()&&q.back().val<=max1[i][j])    //将比当前值小的数全删掉
                q.pop_back();                        
                q.push_back(Node(max1[i][j],j));         //继续进队 
        }

        for(int j=k;j<=m;j++)
        {
            int left=j-k+1;
            while(q.size()&&q.back().val<=max1[i][j])    //将比当前值小的数全删掉
                q.pop_back();
                q.push_back(Node(max1[i][j],j));

            while(q.size()&&q.front().id<left)            //将超出的值删掉
                q.pop_front();
                max1[i][j]=q.front().val;
        }
    }                                             

    ll ans=0;     
    for(int j=k;j<=m;j++)                                //列进行预处理。 
    {
        deque<Node>q;    
        for(int i=1;i<=k-1;i++)
        {
            while(q.size()&&q.back().val<=max1[i][j])//将比当前值小的数全删掉
                q.pop_back();
            q.push_back(Node(max1[i][j],i));
        }

        for(int i=k;i<=n;i++)
        {
            int left=i-k+1;
            while(q.size()&&q.back().val<=max1[i][j])//将比当前值小的数全删掉
                q.pop_back();
            q.push_back(Node(max1[i][j],i));
            while(q.size()&&q.front().id<left)//将超出的值删掉
                q.pop_front();    
            ans+=q.front().val;
        }
    }
    cout<<ans<<endl; 
    return 0;
}