题解 P2216 【[HAOI2007]理想的正方形】
sshwy
2018-12-08 11:19:05
# 题意
有一个$a\times b$的整数组成的矩阵，现请你从中找出一个$n\times n$的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
# 分析
好多人用什么倍增的算法，还有用线段树的。。。
我们考虑一下，要求以$(i,j)$为右下角的$n\times n$的正方形中的最大值和最小值（以最大值为例）
## 暴力
$n^2$暴力，总复杂度$O(abn^2)$.
## 暴力DP
$f[i][j][k]$表示$(i,j)$为右下角，$k\times k$的正方形中的最大值。
$$
f[i][j][k]=max(f[i][j-1][k-1],f[i-1][j][k-1],f[i-1][j-1][k-1])
$$
复杂度$O(abn)$.
## 倍增DP
$f[i][j][k]$表示$(i,j)$为右下角，$2^k\times2^k$的正方形中的最大值
$$
f[i][j][k]=max(f[i][j][k-1],f[i-2^{k-1}][j][k-1],f[i][j-2^{k-1}][k-1],f[i-2^{k-1}][j-2^{k-1}][k-1])
$$
复杂度$O(ablog_2n)$.
## 单调队列
没错，这就是我要讲的算法
受到暴力DP的启发，我们发现暴力DP用了三个边长小1的正方形来更新当前的正方形
而这有点浪费，因为三个正方形有重复部分（即$(i-k+2,j-k+2)$为左上角，$(i-1,j-1)$为右下角的部分）
那么如何优化呢。。。其实我们可以用互不重叠的一组矩形在凑出正方形啊
考虑$d[i,j]$表示以$(i,j)$为右下角，宽度为$n$，高度为$1$的条状矩形中的最大值
显然对于$d[i,1]\cdots d[i,b]$，可以单调队列一起求啊，也就是维护一个从队首到队尾单调递减队列，保证队首下标与当前下标距离不超过n，然后维护一下
那么有了$d[i][j]$，我们再用$d[i][j]$来一次纵向的宽度为$1$，高度为$n$的条状矩形中的最大值不就完了吗
复杂度$O(ab)$呢
最后，本座为了避免写太多代码，求了$d[i][j]$之后，横竖交换，再求一次横向的即可
# 代码
```cpp
#include<cstdio>
#include<cctype>
#include<algorithm>
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
const int N=1003;
int a,b,n,ans=0x3f3f3f3f;
int c[N][N],d[N][N],g[N][N],h[N][N],f[N][N];
//快读
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++;
}
int rd(){
int res=0;char c=nc();
while(!isdigit(c))c=nc();
while(isdigit(c))res=res*10+c-'0',c=nc();
return res;
}
int calc1(int * v,int * ans){//单调队列计算v[i-n+1..i]的最大值，保存在ans[i]中
int q[N*2][2],l=1,r=0;
FOR(i,1,b){
while(l<=r&&q[r][0]<=v[i])r--;
while(l<=r&&q[l][1]+n<=i)l++;
q[++r][0]=v[i],q[r][1]=i;
ans[i]=q[l][0];
}
}
int calc2(int * v,int * ans){//单调队列计算v[i-n+1..i]的最小值，保存在ans[i]中
int q[N*2][2],l=1,r=0;
FOR(i,1,b){
while(l<=r&&q[r][0]>=v[i])r--;
while(l<=r&&q[l][1]+n<=i)l++;
q[++r][0]=v[i],q[r][1]=i;
ans[i]=q[l][0];
}
}
int main(){
a=rd(),b=rd(),n=rd();
FOR(i,1,a)FOR(j,1,b)c[i][j]=rd();//读入
FOR(i,1,a)calc1(c[i],d[i]),calc2(c[i],h[i]);//横向计算最大最小
FOR(i,1,a)FOR(j,i+1,b)swap(d[i][j],d[j][i]),swap(h[i][j],h[j][i]);//横竖交换
swap(a,b);//横竖交换，之前的横向的最大最小变成了纵向的最大最小
FOR(i,1,a)calc1(d[i],g[i]),calc2(h[i],f[i]);//在之前算出的结果上再次横向计算，得到正方形的最大最小
FOR(i,n,a)FOR(j,n,b)ans=min(ans,g[i][j]-f[i][j]);//统计答案
printf("%d",ans);
return 0;
}
```