[HAOI2007]理想的正方形 单调队列 暴力

Code:

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

#define maxn 1002

#define ll long long

#define inf 100000000000

int minv[maxn][maxn], maxv[maxn][maxn];

struct Node{

    ll val;

    int pos;

    Node(ll val=0,int pos=0):val(val),pos(pos){}

};

deque<Node>Q[2];

int main(){

    //freopen("input.in","r",stdin);

    int a,b,n;

    ll ans=inf,p;

    scanf("%d%d%d",&a,&b,&n);

    for(int i=1;i<=a;++i){

        for(int j=1;j<=b;++j) {

            scanf("%lld",&p);

            while(!Q[0].empty()&&Q[0].front().pos<j-n+1)Q[0].pop_front();

            while(!Q[1].empty()&&Q[1].front().pos<j-n+1)Q[1].pop_front();

            while(!Q[0].empty()&&Q[0].back().val>=p) Q[0].pop_back();

            while(!Q[1].empty()&&Q[1].back().val<=p) Q[1].pop_back();

            Q[0].push_back(Node(p,j)),Q[1].push_back(Node(p,j));

            if(j>=n) minv[i][j]=Q[0].front().val, maxv[i][j]=Q[1].front().val;

        }

        while(!Q[0].empty())Q[0].pop_back();

        while(!Q[1].empty())Q[1].pop_back();

    }

    for(int i=n;i<=b;++i){

        for(int j=1;j<=a;++j){

            while(!Q[0].empty()&&Q[0].front().pos<j-n+1)Q[0].pop_front();

            while(!Q[1].empty()&&Q[1].front().pos<j-n+1)Q[1].pop_front();

            while(!Q[0].empty()&&Q[0].back().val>=minv[j][i]) Q[0].pop_back();

            while(!Q[1].empty()&&Q[1].back().val<=maxv[j][i]) Q[1].pop_back();

            Q[0].push_back(Node(minv[j][i],j)),Q[1].push_back(Node(maxv[j][i],j));

            if(j>=n) ans=min(ans,Q[1].front().val-Q[0].front().val);

        }

        while(!Q[0].empty())Q[0].pop_back();

        while(!Q[1].empty())Q[1].pop_back();

    }

    printf("%lld",ans);

    return 0;

}