【题意】

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

的差最小。

【题解】

　　单调队列。

　　设原来的矩阵为$a[i][j]$.

　　先用单调队列处理出每个位置的$b[i][j]=min(a[i][k])，k=j-x+1 --> j$.

　　再用单调队列处理出每个位置的$c[i][j]=min(c[k][i])，k=i-x+1 --> i$.

　　这样$c[i][j]$就是以$i,j$为右下角端点的$x*x$的正方形区域内的最小值。

　　同理处理出最大值，就可以解决这道题了。

　　

#include
     
      #include
      
       #define N 1010#define rg registerusing namespace std;int n,m,x,front,rear,a[N][N],b[2][N][N],c[2][N][N];struct queue{	int pos,d;}q[N];inline int read(){	int k=0,f=1; char c=getchar();	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();	while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();	return k*f;} inline int max(int x,int y){return x>y?x:y;}int main(){	n=read(); m=read(); x=read();	for(rg int i=1;i<=n;i++)		for(rg int j=1;j<=m;j++) a[i][j]=read();	for(rg int j=1;j<=n;j++){		b[0][j][front=rear=1]=q[1].d=a[j][1]; q[1].pos=1;		for(rg int i=2;i<=m;i++){			while(front<=rear&&q[front].pos
       
        =front&&q[rear].d
        
         =front&&q[rear].d>a[j][i]) rear--;			q[++rear]=(queue){i,a[j][i]};			b[1][j][i]=q[front].d;		}	}	for(rg int j=1;j<=m;j++){		c[0][front=rear=1][j]=q[1].d=b[0][1][j]; q[1].pos=1;		for(rg int i=2;i<=n;i++){			while(front<=rear&&q[front].pos
         
          =front&&q[rear].d
          
           =front&&q[rear].d>b[1][i][j]) rear--; q[++rear]=(queue){i,b[1][i][j]}; c[1][i][j]=q[front].d; } } int ans=0X7f7f7f7f; for(rg int i=x;i<=n;i++) for(rg int j=x;j<=m;j++) ans=min(ans,c[0][i][j]-c[1][i][j]); printf("%d\n",ans); return 0;}