题解 P2216 【[HAOI2007]理想的正方形】
小黑AWM
2019-03-28 23:48:49
做掉这题挺不容易的，是从试练场的单调队列关点进来的，但是看到题目第一秒想到的是二维St表……阅读时建议直接跳转至思路。仔细地翻了一下题解单调队列里基本都是把预处理和计算分开的，我这种写法好像没有，自己觉得我的逻辑比较清晰一些。
虽然之后看到很多巨佬都成功的使用改进后的二维st表切了这题，但是直接yy板子的我因MLE只拿了20分。
##### 二维st表模板/不能AC
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define reg register
#define type int//看情况修改返回类型
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline type read()
{
bool minus=false;
char ch=nc();type sum=0;
while(!(ch>='0'&&ch<='9')&&ch!='-')ch=nc();
if(ch=='-')minus=true,ch=nc();//判负没必要的时候记得删，影响效率
while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+ch-48,ch=nc();
return sum;
}
const int maxn = 1e3 + 10;
const int maxlog = 10 + 1;
const int INF = 0x7fffffff;
int n, m, k;
int a[maxn][maxn];
int st1[maxn][maxn][maxlog][maxlog], st2[maxn][maxn][maxlog][maxlog];
int Log2[maxn];
inline int query1(int x1, int y1, int x2, int y2)
{
int k1 = Log2[x2 - x1 + 1], k2 = Log2[y2 - y1 + 1];
return max(st1[x1][y1][k1][k2], max(st1[x2-(1<<k1)+1][y1][k1][k2], max(st1[x1][y2-(1<<k2)+1][k1][k2], st1[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2])));
}
inline int query2(int x1, int y1, int x2, int y2)
{
int k1 = Log2[x2 - x1 + 1], k2 = Log2[y2 - y1 + 1];
return min(st2[x1][y1][k1][k2], min(st2[x2-(1<<k1)+1][y1][k1][k2], min(st2[x1][y2-(1<<k2)+1][k1][k2], st2[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2])));
}
int main()
{
n = read(), m = read(), k = read();
for(int i = 2; i <= max(n, m); i++){
if((1 << (Log2[i-1]+1)) > i)
Log2[i] = Log2[i-1];
else
Log2[i] = Log2[i-1]+1;
}
for (reg int i = 1 ; i <= n ; ++i)
for (reg int j = 1 ; j <= m ; ++j)
st2[i][j][0][0] = st1[i][j][0][0] = a[i][j] = read();
for (reg int p = 0 ; p <= 10 ; p ++)
for (reg int q = 0 ; q <= 10 ; q ++)
if (p != 0 || q != 0){
for (reg int i = 1 ; i + (1<<p) - 1 <= n ; i ++)
for (reg int j = 1 ; j + (1<<q) - 1 <= m ; j ++)
if (!p) st1[i][j][p][q] = max(st1[i][j][p][q - 1], st1[i][j+(1<<(q-1))][p][q - 1]);
else st1[i][j][p][q] = max(st1[i][j][p-1][q], st1[i+(1<<(p-1))][j][p-1][q]);
}//i走p次方，q走j次方for (reg int p = 0 ; p <= 10 ; p ++)
for (reg int p = 0 ; p <= 10 ; p ++)
for (reg int q = 0 ; q <= 10 ; q ++)
if (p != 0 || q != 0)
for (reg int i = 1 ; i + (1<<p) - 1 <= n ; i ++)
for (reg int j = 1 ; j + (1<<q) - 1 <= m ; j ++)
if (!p) st2[i][j][p][q] = min(st2[i][j][p][q - 1], st2[i][j+(1<<(q-1))][p][q - 1]);
else st2[i][j][p][q] = min(st2[i][j][p-1][q], st2[i+(1<<(p-1))][j][p-1][q]);
int ans = INF;
for(int i = 1; i <= n - k + 1; i++){
for(int j = 1; j <= m - k + 1; j++){
int temp = query1(i, j, i + k - 1, j + k - 1) - query2(i, j, i + k - 1, j + k - 1);
ans = min(temp, ans);
}
}
cout << ans << endl;
return 0;
}
```
上述算法时间复杂度$O(N*M*logN*logM)$空间复杂度与时间复杂度相同，不过由于空间复杂度略大，该算法MLE，改进后可以利用正方形边长相等的性质省去一维$O(LogN)$达到极大的节约空间的目的从而AC本题，以上代码的存在价值仅为读者提供可直接套用的二维st表模板，不作冗余讲解，如需讲解可转阅他人题解。
惫懒的我虽然知道正方形的性质但是自然是不愿意继续想这个卡满的劣质算法的。于是回到单调队列，对于单调队列的讲解，可以参考我的另一篇题解[单调队列-最大子段和](https://andrewwayne.blog.luogu.org/solution-p1115)，个人认为讲的还是不错的，欢迎各位指正。
B克曾经告诉过我，单调队列可以解决询问没有重复区间的RMQ问题。引入思考，本问题实际也不过是一种变相的二维RMQ问题，再枚举$N*M$个点罢了。对于一个正方形我们可以轻松地用单调队列处理出每一行的最大值最小值，然后再对于每一行的值在列上处理出最大值与最小值即可。
规定$Aque1[i]$为一个单调队列维护了第i行中的最小值，$Aque2[i]$为最大值，$Bque1$表示维护到第i列$min(Aque1[1 \dots n])$$Bque2$为$max( Aque2[1 \dots n])$
然后我们枚举正方向的右下角标$(j,i)$枚举的时候可以同时处理出最大值和最小值，最终每个点在Aque中最多进一次出一次，所以总复杂度$O(N*M)$仔细地翻了一下题解发现都是把预处理和计算分开的，但其实并没有这个必要，为了节约空间我们可以直接在枚举点的时候更新，实现中的思路在代码中有注释。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e3 + 10;
int N, M, L, A[MAXN][MAXN];
deque<pair<int,int> > Aque1[MAXN], Aque2[MAXN], Bque1, Bque2;//定义如上文所述
int ANS = 0x7fffffff;
int main(){
cin >> N >> M >> L;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
cin >> A[i][j];
int val = 0;
for(int i = 1; i <= M; i++){
Bque1.clear();
Bque2.clear();//清空是很有必要的，由于每进入新的一列都是一个新的Bque，与上一列的值无关，而每一轮结束后并不一定能够使所有元素出队。
for(int j = 1; j <= N; j++){//我的扫描方式类似于一个矩阵一列一列的竖着推进过去
while(!Aque1[j].empty() && Aque1[j].front().first <= i - L)
Aque1[j].pop_front();//抛弃过期决策
while(!Aque2[j].empty() && Aque2[j].front().first <= i - L)
Aque2[j].pop_front();
while(!Bque1.empty() && Bque1.front().first <= j - L)
Bque1.pop_front();
while(!Bque2.empty() && Bque2.front().first <= j - L)
Bque2.pop_front();
while(!Aque1[j].empty() && Aque1[j].back().second > A[j][i])
Aque1[j].pop_back();
Aque1[j].push_back(make_pair(i, A[j][i]));
while(!Aque2[j].empty() && Aque2[j].back().second < A[j][i])
Aque2[j].pop_back();
Aque2[j].push_back(make_pair(i, A[j][i]));//抛弃不优决策，保证维护出A[j][i-L+1] ～ A[j]i]中的最优决策点
while(!Bque1.empty() && Bque1.back().second > Aque1[j].front().second)
Bque1.pop_back();
Bque1.push_back(make_pair(j, Aque1[j].front().second));
while(!Bque2.empty() && Bque2.back().second < Aque2[j].front().second)
Bque2.pop_back();
Bque2.push_back(make_pair(j, Aque2[j].front().second));//维护出Aque[j-L+1] ～ Aque[j]之间的最优决策
if(i >= L && j >= L)//若是右下角表过小不成正方形则不记录
ANS = min(ANS, Bque2.front().second - Bque1.front().second);
}
}
cout << ANS << endl;
return 0;
}
```
思路应该是属于较容易想到的，唯独利用一个维护列上的单调队列来维护行队列的有一丝妙处。时间复杂度严格$O(N*M)$不过因为我滥用STL和cin所以常数大到飞起所以总时间并不是很快。OI之乐便是在于经过一番苦思之后想到最优解和多解吧。