[BZOJ 1047][HAOI 2007]理想的正方形(二维滑动窗口+单调队列)

?

思路：裸的二维上的滑动窗口问题，可以借鉴一维滑动窗口的思路。首先预处理出每一列j的、以第i行元素为结尾、长度为n的区间的最大值maxv[i][j]、最小值minv[i][j]，然后再搞每一行，求出以每一行i结尾、行标上长度为n的区间、以第j列结尾、列标上长度为n的区间得到的二维区间最大值与最小值之差，遍历每一行得到这个差的最小值即为答案。

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAXN 1200 #define INF 0x3f3f3f3f using namespace std; struct node { int val; //这个元素的值 int pos; //这个元素的下标 }q1[MAXN],q2[MAXN]; //q1维护一个单调递减队列，q2维护一个单调递增对了队列 int map[MAXN][MAXN]; int maxv[MAXN][MAXN],minv[MAXN][MAXN]; int pa,pb,n; //pa*pb大小的矩阵,从中取n*n大小的子矩阵 void init() { scanf(%d%d%d,&pa,&pb,&n); for(int i=1;i<=pa;i++) for(int j=1;j<=pb;j++) scanf(%d,&map[i][j]); } void work1() //第一次操作维护每一列的最值，最终得到第j列以第i个元素结尾的长度为n的区间的最大值、最小值 { int h1,t1,h2,t2; //队尾与队首的指针 for(int j=1;j<=pb;j++) //枚举列号j { h1=h2=t1=t2=0; for(int i=1;i<=pa;i++) //枚举长度为n的区间的最后一个元素下标i,当前长度为n的区间为[i-n+1,i { //维护队列q1 while(h1
       
        =map[i][j]) //把队尾不满足单调性的都弹掉 t2--; q2[++t2].val=map[i][j]; q2[t2].pos=i; if(i
        
         =minv[i][j]) //把队尾不满足单调性的都弹掉 t2--; q2[++t2].val=minv[i][j]; q2[t2].pos=j; if(i>=n&&j>=n) ans=min(ans,q1[h1+1].val-q2[h2+1].val); } } printf(%d ,ans); } int main() { init(); work1(); work2(); return 0; } 
        
       
      
     
    
   
  

?

?