洛谷 P2216 [HAOI2007]理想的正方形 || 二维RMQ的单调队列

题目

这个题的算法核心就是求出以i,j为左上角，边长为n的矩阵中最小值和最大值。最小和最大值的求法类似。

单调队列做法：

以最小值为例：

q1[i][j]表示第i行上，从j列开始的n列的最小值。
$q1[i][j]=min(x[i][j],x[i][j+1],...,x[i][j+n-1])$
$q1[i][1]=min(x[i][1],x[i][2],...,x[i][n])$
$q1[i][2]=min(x[i][2],x[i][3],...,x[i][n+1])$
类似滑动窗口，因此直接枚举行，对于每一行单调队列处理即可。

q2[i][j]表示以第i行第j列为左上角的边长为n的矩阵的最小值
$q2[i][j]=min(q1[i][j],q1[i+1][j],...,q1[i+n-1][j])$
$q2[1][j]=min(q1[1][j],q1[2][j],...,q1[n][j])$
$q2[2][j]=min(q1[2][j],q1[3][j],...,q2[n+1][j])$
显然又可以用单调队列处理。总时间复杂度$O(n^2)$

（额外）更简短的做法（二维ST表，$O(n^2\;log\;n)$）：

（由于要求的是正方形，因此可以$O(n^2\;log\;n)$，一般应该是$O({(n\;log\;n)}^2)$）

用f[i][j][k]来表示横纵坐标分别为i,j开始到i+2^k-1,j+2^k-1的整个矩阵（正方形）中的最大值

https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2216

笔记：

1.这道题一开始想到了可能跟单调队列有关系，但是并没有想清楚。想了很久后，把q1和q2的关系式列了出来，一切就明朗了。

2.求最小值的单调队列队首(l)最小，队尾(r)最大，l<r。求最大值的单调队列队首(l)最大，队尾(r)最小，l<r。

求最小值的单调队列
2 3 5 4 6 1
1. 2
2. 2 3
3. 2 3 5
4. 2 3 4
5. 2 3 4 6
6. 1

3.单调队列的调试还算方便，只需要开着对单调队列的变量查看，观察内部元素是否正常就行了。

 #include<cstdio>

 #define min(a,b) ((a)>(b)?(b):(a))

 typedef long long LL;

 LL a,b,n;

 LL x[][];

 LL q1min[][],q1max[][],q2min[][],q2max[][];

 LL tmpmin[],tmpmax[],lmin,rmin,lmax,rmax,anss=0x3f3f3f3f3f3f3f3f;

 int main()

 {

     LL i,j;

     scanf("%lld%lld%lld",&a,&b,&n);

     for(i=;i<=a;i++)

         for(j=;j<=b;j++)

             scanf("%lld",&x[i][j]);

     for(i=;i<=a;i++)

     {

         lmin=rmin=lmax=rmax=;

         for(j=;j<=n;j++)

         {

             while(rmin>lmin&&x[i][tmpmin[rmin-]]>=x[i][j])    rmin--;

             tmpmin[rmin++]=j;

             while(rmax>lmax&&x[i][tmpmax[rmax-]]<=x[i][j])    rmax--;

             tmpmax[rmax++]=j;

         }

         q1min[i][]=x[i][tmpmin[lmin]];

         q1max[i][]=x[i][tmpmax[lmax]];

         for(j=n+;j<=b;j++)

         {

             if(rmin>lmin&&tmpmin[lmin]<=j-n)    lmin++;

             if(rmax>lmax&&tmpmax[lmax]<=j-n)    lmax++;

             while(rmin>lmin&&x[i][tmpmin[rmin-]]>=x[i][j])    rmin--;

             tmpmin[rmin++]=j;

             while(rmax>lmax&&x[i][tmpmax[rmax-]]<=x[i][j])    rmax--;

             tmpmax[rmax++]=j;

             q1min[i][j-n+]=x[i][tmpmin[lmin]];

             q1max[i][j-n+]=x[i][tmpmax[lmax]];

         }

     }

     for(i=;i<=b;i++)

     {

         lmin=rmin=lmax=rmax=;

         for(j=;j<=n;j++)

         {

             while(rmin>lmin&&q1min[tmpmin[rmin-]][i]>=q1min[j][i])    rmin--;

             tmpmin[rmin++]=j;

             while(rmax>lmax&&q1max[tmpmax[rmax-]][i]<=q1max[j][i])    rmax--;

             tmpmax[rmax++]=j;

         }

         q2min[][i]=q1min[tmpmin[lmin]][i];

         q2max[][i]=q1max[tmpmax[lmax]][i];

         for(j=n+;j<=a;j++)

         {

             if(rmin>lmin&&tmpmin[lmin]<=j-n)    lmin++;

             if(rmax>lmax&&tmpmax[lmax]<=j-n)    lmax++;

             while(rmin>lmin&&q1min[tmpmin[rmin-]][i]>=q1min[j][i])    rmin--;

             tmpmin[rmin++]=j;

             while(rmax>lmax&&q1max[tmpmax[rmax-]][i]<=q1max[j][i])    rmax--;

             tmpmax[rmax++]=j;

             q2min[j-n+][i]=q1min[tmpmin[lmin]][i];

             q2max[j-n+][i]=q1max[tmpmax[lmax]][i];

         }

     }

     for(i=;i<=a-n+;i++)

         for(j=;j<=b-n+;j++)

             anss=min(anss,q2max[i][j]-q2min[i][j]);

     printf("%lld",anss);

     return ;

 }

洛谷 P2216 [HAOI2007]理想的正方形 || 二维RMQ的单调队列的相关教程结束。