BZOJ - 1047 理想的正方形(单调队列)

思路

与poj 3690的处理方法非常相似，先利用单调队列处理行长度为n的段的最大最小值，储存在一个数组里，然后在对处理完的数列纵向再跑一次长度为n的单调队列。

代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=1105,MAXSIZE=1000005;
//flag=0->min,1=max
template <typename T>
struct monoqueue{
    int flag;
    T arr[MAXSIZE];
    int head,tail;
    monoqueue(){}
    monoqueue(int flag):flag(flag){
        head=0,tail=0;
    }
    void push(T x){
        if(flag){
            while(head<tail&&arr[tail]<x)tail--;
        }
        else{
            while(head<tail&&arr[tail]>x)tail--;
        }
        arr[++tail]=x;
    }
    void pop(){
        head++;
    }
    int sz(){
        return tail-head;
    }
    void clear(){
        head=0,tail=0;
    }
    bool empty(){
        return tail==0;
    }
    T top(){
        return arr[head+1];
    }
};
monoqueue<int> rowmax(1),rowmin(0),colmax(1),colmin(0);
int mat[MAXN][MAXN],maxrow[MAXN][MAXN],minrow[MAXN][MAXN];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    int a,b,n;
    while(~scanf("%d%d%d",&a,&b,&n)){
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                scanf("%d",&mat[i][j]);
            }
        }
        queue<int> q,qmax,qmin;
        for(int i=0;i<a;i++){
            int j=0;
            for(;j<n;j++){
                rowmax.push(mat[i][j]);
                rowmin.push(mat[i][j]);
                q.push(mat[i][j]);
            }
            maxrow[i][j-1]=rowmax.top();
            minrow[i][j-1]=rowmin.top();
            for(;j<b;j++){
                if(rowmax.top()==q.front())rowmax.pop();
                if(rowmin.top()==q.front())rowmin.pop();
                q.pop();
                q.push(mat[i][j]);
                rowmax.push(mat[i][j]);
                rowmin.push(mat[i][j]);
                maxrow[i][j]=rowmax.top();
                minrow[i][j]=rowmin.top();
            }
            rowmax.clear();
            rowmin.clear();
            while(!q.empty())q.pop();
        }
        int diff=INTINF;
        for(int j=n-1;j<b;j++){
            int i=0;
            for(;i<n;i++){
                colmax.push(maxrow[i][j]);
                colmin.push(minrow[i][j]);
                qmax.push(maxrow[i][j]);
                qmin.push(minrow[i][j]);
            }
            diff=min(diff,colmax.top()-colmin.top());
            for(;i<a;i++){
                if(colmax.top()==qmax.front())colmax.pop();
                if(colmin.top()==qmin.front())colmin.pop();
                qmax.pop(),qmin.pop();
                qmax.push(maxrow[i][j]);
                qmin.push(minrow[i][j]);
                colmax.push(maxrow[i][j]);
                colmin.push(minrow[i][j]);
                diff=min(diff,colmax.top()-colmin.top());
            }
            colmax.clear();
            colmin.clear();
            while(!qmax.empty())qmax.pop();
            while(!qmin.empty())qmin.pop();
        }
        printf("%d\n",diff);
    }
    return 0;
}