2019牛客暑期多校训练营（第三场）F Planting Trees【单调队列】

题目链接：https://ac.nowcoder.com/acm/contest/883/F
题解：

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int N,M;
int a[505][505];
int queinc[505],quedec[505];//用数组模拟单调队列
int minn[505],maxx[505];
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>N>>M;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                cin>>a[i][j];
            }
        }
        int ans=0;
        for(int i=1;i<=N;i++){
            for(int kk=1;kk<=N;kk++){
                minn[kk]=INF;
                maxx[kk]=0;
            }

            for(int j=i;j<=N;j++){
                int pre=0;
                int linc=0,rinc=-1;
                int ldec=0,rdec=-1;
                for(int k=1;k<=N;k++){
                    minn[k]=min(a[j][k],minn[k]);
                    maxx[k]=max(a[j][k],maxx[k]);
                    while(ldec<=rdec&&maxx[quedec[rdec]]<=maxx[k]){
                        rdec--;
                    }
                    quedec[++rdec]=k;
                    while(linc<=rinc&&minn[queinc[rinc]]>=minn[k]){
                        rinc--;
                    }
                    queinc[++rinc]=k;

                    while(linc<=rinc&&ldec<=rdec&&(maxx[quedec[ldec]]-minn[queinc[linc]])>M){
                        pre=min(quedec[ldec],queinc[linc]);
                        if(quedec[ldec]<queinc[linc]){
                            ldec++;
                        }
                        else if(quedec[ldec]>queinc[linc]){
                            linc++;
                        }
                        else{
                            linc++;
                            ldec++;
                        }
                    }
                    if(linc<=rinc||ldec<=rdec){
                        ans=max(ans,(j-i+1)*(k-pre));
                    }
                    else{
                        pre=k;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
2
2 0
1 2
2 1
3 1
1 3 2
2 3 1
3 2 1
*/