单调队列好东西。。。。

先跑第一遍处理出每行以（x，y）结尾长度为n的一段的max与min

再跑一遍处理出每列以（x，y）结尾长度为n的一段的max的max以及min的min

1 #include
      
        2 #define lowbit(a) ((a)&(-(a))) 3 #define clr(a,x) memset(a,x,sizeof(a)) 4 #define rep(i,l,r) for(int i=l;i<(r);i++) 5 typedef long long ll; 6 using namespace std; 7 int read() 8 { 9     char c=getchar();10     int ans=0,f=1;11     while(!isdigit(c)){12         if(c=='-') f=-1;13         c=getchar();14     }15     while(isdigit(c)){16         ans=ans*10+c-'0';17         c=getchar();18     }19     return ans*f;20 }21 const int maxa=1009,maxb=1009,inf=0x7fffffff;22 int a,b,n,A[maxa][maxb],mn[maxa][maxb],mx[maxa][maxb];23 int main()24 {    25     a=read(),b=read(),n=read();26     rep(i,0,a){27         rep(j,0,b) A[i][j]=read();28     }29     rep(i,0,a){30         deque
       
        Qmax,Qmin;31         rep(j,0,b){32             while(!Qmax.empty()&&Qmax.front()
        
         =A[i][j]) Qmin.pop_back();36             Qmax.push_back(j);Qmin.push_back(j);37             if(j>=n-1) mx[i][j]=A[i][Qmax.front()],mn[i][j]=A[i][Qmin.front()];38         }39     }40     int ans=inf;41     rep(i,n-1,b){42         deque
         
          Qmax,Qmin;43         rep(j,0,a){44             while(!Qmax.empty()&&Qmax.front()
          
           =mn[j][i]) Qmin.pop_back();48             Qmax.push_back(j);Qmin.push_back(j);49             if(j>=n-1) ans=min(ans,mx[Qmax.front()][i]-mn[Qmin.front()][i]);50         }51     }52     printf("%d\n",ans);53     return 0;54 }
          
         
        
       
      

1047: [HAOI2007]理想的正方形

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2062  Solved: 1095

[][][]

Description

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

Input

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

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

HINT

 

问题规模

（1）矩阵中的所有数都不超过1,000,000,000

（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10

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

 

Source

 

[ ][ ][ ]