BZOJ 1047: [HAOI2007]理想的正方形 单调队列瞎搞

时间：2022-09-07 21:24:37

题意很简明吧？

枚举的矩形下边界和右端点即右下角，来确定矩形位置；

每一个纵列开一个单调队列，记录从 i-n+1 行到 i 行每列的最大值和最小值，矩形下边界向下推移的时候维护一下；

然后在记录的每一列的最大值和最小值上，跑滑动窗口，即用单调队列维护区间 [ j-n+1 , j ] 的最大值和最小值；

相当于维护了一个矩形的最大值和最小值

#include<cstdio>

#include<iostream>

#include<queue>

#define R register int

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

inline int abs(int x) {return x>?x:-x;}

int a,b,n,ans=0x3f3f3f3f;

int vl[][];

deque<int> q[],qq[],p,pp;

signed main() {

    a=g(),b=g(),n=g();

    for(R i=;i<=a;++i) for(R j=;j<=b;++j) vl[i][j]=g();

    for(R i=;i<=a;++i) {

        for(R j=;j<=b;++j) {

            while(q[j].size()&&vl[q[j].back()][j]<vl[i][j]) q[j].pop_back();

            while(q[j].size()&&q[j].front()+n<=i) q[j].pop_front();

            q[j].push_back(i);

            //cout<<i<<"hang"<<j<<"lie"<<vl[i][q[j].front()]<<" ";

            //cout<<"mx"<<vl[q[j].front()][j]<<" ";

        }

        for(R j=;j<=b;++j) {

            while(qq[j].size()&&vl[qq[j].back()][j]>vl[i][j]) qq[j].pop_back();

            while(qq[j].size()&&qq[j].front()+n<=i) qq[j].pop_front();

            qq[j].push_back(i);

            //cout<<"mn"<<vl[qq[j].front()][j]<<" ";

        }//cout<<'\n';

        if(i<n) continue;

        p.clear();pp.clear();

        for(R j=;j<=b;++j) {

            while(p.size()&&vl[q[p.back()].front()][p.back()]<vl[q[j].front()][j]) p.pop_back();

            while(p.size()&&p.front()+n<=j) p.pop_front();

            p.push_back(j);

            while(pp.size()&&vl[qq[pp.back()].front()][pp.back()]>vl[qq[j].front()][j]) pp.pop_back();

            while(pp.size()&&pp.front()+n<=j) pp.pop_front();

            pp.push_back(j);

            if(j<n) continue;

            ans=min(abs(vl[q[p.front()].front()][p.front()]-vl[qq[pp.front()].front()][pp.front()]),ans);

        }

    }printf("%d\n",ans);

}

2019.04.06

相关文章