时间限制: 1000 ms         内存限制: 524288 KB

【题目描述】

原题来自：HAOI 2007

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

【输入】

第一行为三个整数，分别表示 a,b,n 的值；

第二行至第 a+1 行每行为 b 个非负整数，表示矩阵中相应位置上的数。

【输出】

输出仅一个整数，为 a×b 矩阵中所有「n×n 正方形区域中的最大整数和最小整数的差值」的最小值。

【输入样例】

5 4 21 2 5 60 17 16 016 17 2 12 10 2 11 2 2 2

【输出样例】

1

【提示】

数据范围与提示：

对于 20% 的数据 2≤a,b≤100,n≤10；

对于 100% 的数据 2≤a,b≤1000,n≤a,n≤b,n≤100，矩阵中的所有数都不超过 10⁹。

 

sol：这题有两种做法（二维ST表，二维单调队列）

二维ST表：顾名思义二维的ST表，ST[i][j][k]表示以（i，j）为左下角，边长为 2^k 的正方形的最值，很好处理

#include 
      
       using namespace std;typedef int ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-');        ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48);        ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-');        x=-x;    }    if(x<10)    {        putchar(x+'0');        return;    }    write(x/10);    putchar((x%10)+'0');    return;}inline void writeln(ll x){    write(x);    putchar('\n');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) writeln(x)const int N=1005,B=10,inf=0x3f3f3f3f;int n,m,K,St_Max[N][N][B],St_Min[N][N][B];inline int Max4(int a,int b,int c,int d){    int e=max(a,b),f=max(c,d); return max(e,f);}inline int Min4(int a,int b,int c,int d){    int e=min(a,b),f=min(c,d); return min(e,f);}int main(){//    freopen("square1.in","r",stdin);    int i,j,k;    R(n); R(m); R(K);    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++) St_Max[i][j][0]=St_Min[i][j][0]=read();    }    for(i=1;i<=7;i++)    {        for(j=1;j+(1<
       
        <=n;j++)        {            for(k=1;k+(1<
        
         <=m;k++)            {                St_Max[j][k][i]=Max4(St_Max[j][k][i-1],St_Max[j+(1<<(i-1))][k][i-1],St_Max[j][k+(1<<(i-1))][i-1],St_Max[j+(1<<(i-1))][k+(1<<(i-1))][i-1]);                St_Min[j][k][i]=Min4(St_Min[j][k][i-1],St_Min[j+(1<<(i-1))][k][i-1],St_Min[j][k+(1<<(i-1))][i-1],St_Min[j+(1<<(i-1))][k+(1<<(i-1))][i-1]);            }        }    }    int ans=inf;    int oo;    for(oo=0;;oo++) if(((1<
         
          <=K)&&((1<<(oo+1))>=K)) break;    for(i=1;i+K-1<=n&&ans;i++)    {        for(j=1;j+K-1<=m&&ans;j++)        {            int o1=Max4(St_Max[i][j][oo],St_Max[i+K-1-(1<
          
           <
           
            <
            
             <
            
           
          
         
        
       
      

二维单调队列：先处理出Min[i][j][0]表示以（i，j）为右下角的长度为n的一整条中的最小值，用单调队列a*b就可以处理出来了

再用Min[i][j][0]到列上去跑单调队列，得到Min[i][j][1]表示以（i，j）为右下角的一个n*n的正方形中的最小值

#include 
      
       using namespace std;typedef int ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-');        ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48);        ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-');        x=-x;    }    if(x<10)    {        putchar(x+'0');        return;    }    write(x/10);    putchar((x%10)+'0');    return;}inline void writeln(ll x){    write(x);    putchar('\n');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) writeln(x)const int N=1005,inf=0x3f3f3f3f;int n,m,L,Val[N][N];int Min[N][N][2],Max[N][N][2];struct Record{    int Shuz,Weiz;}Ddq[N];int main(){//    freopen("square1.in","r",stdin);    int i,j,Head,Tail;    R(n); R(m); R(L);    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++) R(Val[i][j]);    }    for(i=1;i<=n;i++)    {        Head=1; Tail=0;        for(j=1;j<=m;j++)        {            while(Head<=Tail&&Val[i][j]
       
        Ddq[Tail].Shuz) Tail--;            Ddq[++Tail]=(Record){Val[i][j],j};            while(Head
        
         
          Ddq[Tail].Shuz) Tail--;            Ddq[++Tail]=(Record){Max[i][j][0],i};            while(Head