Description

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

的差最小。

Input

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

行相邻两数之间用一空格分隔。

100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000

Output

　　仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

Sample Input

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

Sample Output

1

 

题解：

对于原矩阵每行维护两个单调队列（最大和最小）

然后对得到的max数组和min数组每列再次维护一个单调队列

四次单调队列就ok，弄清楚原理之后这个东西套模板就好

其实就是打一遍然后复制粘贴..

 

代码：

#include 
      
       #define ll int#define inf 1<<30#define max(x,y) x>y?x:y#define min(x,y) x
       
        0?x:-xinline void read(ll &x){    x=0;ll f=1;char c=getchar();    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    x*=f;}using namespace std;#define N 1010ll n,m,len;ll a[N][N];ll q1[N],q2[N];ll MAX[N][N],MIN[N][N];ll L1[N],L2[N],R1[N],R2[N],Q1[N][N],Q2[N][N];ll ans=((1<<30)-1)<<1|1;int main(){    read(n);read(m);read(len);    for(ll i=1;i<=n;i++){        for(ll j=1;j<=m;j++){            read(a[i][j]);        }    }//  mt(L1,1);mt(L2,1);mt(R1,0);mt(R2,0);    for(ll i=1;i<=m;i++)L1[i]=L2[i]=1,R1[i]=R2[i]=0;    for(ll i=1;i<=n;i++){        ll r1=0,l1=1,r2=0,l2=1;        for(ll j=m;j>=1;j--){            MAX[i][j]=MIN[i][j]=a[i][j];            while(l1<=r1&&q1[l1]-j>=len)l1++;            while(l2<=r2&&q2[l2]-j>=len)l2++;            while(l1<=r1&&a[i][j]>a[i][q1[r1]])r1--;            q1[++r1]=j;            if(l1<=r1)MAX[i][j]=max(MAX[i][j],a[i][q1[l1]]);            while(l2<=r2&&a[i][j]
        
         =1;j--){            while(L1[j]<=R1[j]&&i-Q1[j][L1[j]]>=len)L1[j]++;            while(L2[j]<=R2[j]&&i-Q2[j][L2[j]]>=len)L2[j]++;            while(L1[j]<=R1[j]&&MAX[i][j]>MAX[Q1[j][R1[j]]][j])R1[j]--;            while(L2[j]<=R2[j]&&MIN[i][j]
         
          =len){                if(L1[j]<=R1[j]&&L2[j]<=R2[j]){                    ans=min(ans,MAX[Q1[j][L1[j]]][j]-MIN[Q2[j][L2[j]]][j]);                }            }        }    }    printf("%d\n",ans);}