题解：P2216 [HAOI2007] 理想的正方形

原题Link

其实算是一道 ds 吧。

题意

有一个 $a\times b$ 的矩阵，要找出一个 $n\times n$ 的矩阵，使其里面的最大值与最小值的差最小，并输出差值。

Solution

发现有最大值问题与最小值问题，考虑二维 ST 表。

令 $st_{k,i,j}$ 为以 $(i,j)$ 为左上角，大小 $2^k \times 2^k$ 的正方形的最值。

预处理

我们可以分别把长和宽拆成 $2^{k-1}+2^{k-1}$，所以可以得到：

$$st_{k,i,j}=\max\left\{\begin{matrix}st_{k-1,i,j} \\st_{k-1,i,j+2^{k-1}} \\st_{k-1,i+2^{k-1},j} \\st_{k-1,i+2^{k-1},j+2^{k-1}} \end{matrix}\right.$$

查询

假设要求左上角 $(x1,y1)$，右下角 $(x2,y2)$ 的正方形的最值。 令 $k=\lfloor \log_2 L \rfloor$。这里 $L$ 是正方形的边长。依旧把长和宽拆成 $2^{k-1}+2^{k-1}$，可以得到所求值应为：

$$Ans=\max\left\{\begin{matrix}st_{k,x1,y1} \\st_{k,x1,y2-2^k+1} \\st_{k,x2-2^k+1,y1} \\st_{k,x2-2^k+1,y2-2^k+1} \end{matrix}\right.$$

时间复杂度

二维 ST 表，不难根据一维来推出是 $O(n^2 \log n)$。

Code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int a,b,n;
int stmax[15][N][N],stmin[15][N][N];
int ans=0x3f3f3f3f;
int lg[N];
void init(){
	for(int i=2;i<=N;i++){
		lg[i]=lg[i/2]+1;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>a>>b>>n;
	init();
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			int x;
			cin>>x;
			stmax[0][i][j]=stmin[0][i][j]=x;
		}
	}	
	for(int k=1;k<=lg[min(a,b)];k++){
		for(int i=1;i+(1<<k)-1<=a;i++){
			for(int j=1;j+(1<<k)-1<=b;j++){
				stmax[k][i][j]=max({stmax[k-1][i][j],stmax[k-1][i][j+(1<<k-1)],stmax[k-1][i+(1<<k-1)][j],stmax[k-1][i+(1<<k-1)][j+(1<<k-1)]});
				stmin[k][i][j]=min({stmin[k-1][i][j],stmin[k-1][i][j+(1<<k-1)],stmin[k-1][i+(1<<k-1)][j],stmin[k-1][i+(1<<k-1)][j+(1<<k-1)]});
			}
		}
	}	
	for(int i=1;i+n-1<=a;i++){
		for(int j=1;j+n-1<=b;j++){
			int k=lg[n];
			int maxn=max({stmax[k][i][j],stmax[k][i][j+n-(1<<k)],stmax[k][i+n-(1<<k)][j],stmax[k][i+n-(1<<k)][j+n-(1<<k)]});
			int minn=min({stmin[k][i][j],stmin[k][i][j+n-(1<<k)],stmin[k][i+n-(1<<k)][j],stmin[k][i+n-(1<<k)][j+n-(1<<k)]});
			ans=min(ans,maxn-minn);
		}
	}	
	cout<<ans;
	return 0;
}