[BZOJ1047][HAOI2007]理想的正方形 二维单调队列

时间：2020-12-09 06:11:36

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1047

我们对每矩阵的一列维护一个大小为$n$的单调队列，队中元素为矩阵中元素。然后扫描每一行，再次维护一个大小为$n$的单调队列，队中元素为当前列的队列中取出的最值。$O(n^2)$扫过去就可以了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int INF=<<;

 int inline readint(){

     int Num;char ch;

     while((ch=getchar())<''||ch>'');Num=ch-'';

     while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';

     return Num;

 }

 int A,B,N;

 int M[][];

 int qmn1[][],qmn2[][],hmn[],tmn[];

 int qmx1[][],qmx2[][],hmx[],tmx[];

 int Qmn1[],Qmn2[],Hmn,Tmn;

 int Qmx1[],Qmx2[],Hmx,Tmx;

 int main(){

     A=readint();

     B=readint();

     N=readint();

     for(int i=;i<=A;i++)

         for(int j=;j<=B;j++)

             M[i][j]=readint();

     for(int i=;i<=B;i++){

         hmx[i]=hmn[i]=;

         tmx[i]=tmn[i]=;

         for(int j=;j<N;j++){

             while(hmx[i]<=tmx[i]&&qmx1[i][tmx[i]]<=M[j][i]) tmx[i]--;

             qmx1[i][++tmx[i]]=M[j][i];

             qmx2[i][tmx[i]]=j;

             while(hmn[i]<=tmn[i]&&qmn1[i][tmn[i]]>=M[j][i]) tmn[i]--;

             qmn1[i][++tmn[i]]=M[j][i];

             qmn2[i][tmn[i]]=j;

         }

     }

     int ans=INF;

     for(int i=N;i<=A;i++){

         for(int j=;j<=B;j++){

             while(hmx[j]<=tmx[j]&&qmx2[j][hmx[j]]+N<=i) hmx[j]++;

             while(hmx[j]<=tmx[j]&&qmx1[j][tmx[j]]<=M[i][j]) tmx[j]--;

             qmx1[j][++tmx[j]]=M[i][j];

             qmx2[j][tmx[j]]=i;

             while(hmn[j]<=tmn[j]&&qmn2[j][hmn[j]]+N<=i) hmn[j]++;

             while(hmn[j]<=tmn[j]&&qmn1[j][tmn[j]]>=M[i][j]) tmn[j]--;

             qmn1[j][++tmn[j]]=M[i][j];

             qmn2[j][tmn[j]]=i;

         }

         Hmx=Hmn=;

         Tmx=Tmn=;

         for(int j=;j<N;j++){

             while(Hmx<=Tmx&&Qmx1[Tmx]<=qmx1[j][hmx[j]]) Tmx--;

             Qmx1[++Tmx]=qmx1[j][hmx[j]];

             Qmx2[Tmx]=j;

             while(Hmn<=Tmn&&Qmn1[Tmn]>=qmn1[j][hmn[j]]) Tmn--;

             Qmn1[++Tmn]=qmn1[j][hmn[j]];

             Qmn2[Tmn]=j;

         }

         for(int j=N;j<=B;j++){

             while(Hmx<=Tmx&&Qmx2[Hmx]+N<=j) Hmx++;

             while(Hmx<=Tmx&&Qmx1[Tmx]<=qmx1[j][hmx[j]]) Tmx--;

             Qmx1[++Tmx]=qmx1[j][hmx[j]];

             Qmx2[Tmx]=j;

             while(Hmn<=Tmn&&Qmn2[Hmn]+N<=j) Hmn++;

             while(Hmn<=Tmn&&Qmn1[Tmn]>=qmn1[j][hmn[j]]) Tmn--;

             Qmn1[++Tmn]=qmn1[j][hmn[j]];

             Qmn2[Tmn]=j;

             ans=min(ans,Qmx1[Hmx]-Qmn1[Hmn]);

         }

     }

     printf("%d\n",ans);

     return ;

 }

相关文章