Luogu | P2216 [HAOI 2007] 理想的正方形 | 数据结构 | 单调队列


Description

有一个 $a\times b$ 的整数组成的矩阵,现请你从中找出一个 $n \times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。


Input Format

第一行为 $3$ 个整数,分别表示 $a,b,n$ 的值。

第二行至第 $a+1$ 行每行为 $b$ 个非负整数,表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。


Output Format

仅一个整数,为 $a\times b$ 矩阵中所有 $n\times n$ 正方形区域中的最大整数和最小整数的差值的最小值。


Input Sample

Sample 01

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2


Output Sample

Sample 01

1


Data Range

$m_i \in [1,10^9]$,$a , b \in [2,10^3]$,$n \in [1,\min(100,\min(a,b))]$。


Solution

用一次单调队列(滑动窗口)维护行,生成 mimx 表示以 $(i,j)$ 为左上角的 $1 \times n$ 的长方形的最值。

再在 mimx 上用一次单调队列(滑动窗口)维护列,生成 MiMx 表示以 $(i,j)$ 为左上角的 $n \times n$ 的正方形的最值。


Code

#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::deque;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct dt{
    int pos;
    int val;
};

int N;
int M;
int K;
int ans=0x7f7f7f7f;

int mt[1005][1005];
int mx[1005][1005];
int mi[1005][1005];
int Mx[1005][1005];
int Mi[1005][1005];

deque<dt>dq;

int main(){
    Read(N);
    Read(M);
    Read(K);
    rep(i,1,N)
    rep(j,1,M)
        Read(mt[i][j]);
    rep(i,1,N){
        while(!dq.empty())
            dq.pop_front();
        rep(j,1,K-1){
            while(!dq.empty()&&dq.back().val>mt[i][j])
                dq.pop_back();
            dq.push_back((dt){j,mt[i][j]});
        }
        rep(j,K,M){
            while(!dq.empty()&&dq.front().pos<=j-K)
                dq.pop_front();
            while(!dq.empty()&&dq.back().val>mt[i][j])
                dq.pop_back();
            dq.push_back((dt){j,mt[i][j]});
            mi[i][j-K+1]=dq.front().val;
        }
    }
    rep(i,1,N){
        while(!dq.empty())
            dq.pop_front();
        rep(j,1,K-1){
            while(!dq.empty()&&dq.back().val<mt[i][j])
                dq.pop_back();
            dq.push_back((dt){j,mt[i][j]});
        }
        rep(j,K,M){
            while(!dq.empty()&&dq.front().pos<=j-K)
                dq.pop_front();
            while(!dq.empty()&&dq.back().val<mt[i][j])
                dq.pop_back();
            dq.push_back((dt){j,mt[i][j]});
            mx[i][j-K+1]=dq.front().val;
        }
    }
    rep(j,1,M-K+1){
        while(!dq.empty())
            dq.pop_front();
        rep(i,1,K-1){
            while(!dq.empty()&&dq.back().val>mi[i][j])
                dq.pop_back();
            dq.push_back((dt){i,mi[i][j]});
        }
        rep(i,K,N){
            while(!dq.empty()&&dq.front().pos<=i-K)
                dq.pop_front();
            while(!dq.empty()&&dq.back().val>mi[i][j])
                dq.pop_back();
            dq.push_back((dt){i,mi[i][j]});
            Mi[i-K+1][j]=dq.front().val;
        }
    }
    rep(j,1,M-K+1){
        while(!dq.empty())
            dq.pop_front();
        rep(i,1,K-1){
            while(!dq.empty()&&dq.back().val<mx[i][j])
                dq.pop_back();
            dq.push_back((dt){i,mx[i][j]});
        }
        rep(i,K,N){
            while(!dq.empty()&&dq.front().pos<=i-K)
                dq.pop_front();
            while(!dq.empty()&&dq.back().val<mx[i][j])
                dq.pop_back();
            dq.push_back((dt){i,mx[i][j]});
            Mx[i-K+1][j]=dq.front().val;
        }
    }
    rep(i,1,N-K+1)
        rep(j,1,M-K+1)
            ans=min(ans,Mx[i][j]-Mi[i][j]);
    printf("%d\n",ans);
    return 0;
}