[Bzoj1047][HAOI2007]理想的正方形(ST表)

时间:2020-12-09 06:11:42

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

题目虽然有一个n的限制,但求二维区间最值首先想到的还是RMQ,但是如果按照往常RMQ的写法,空间复杂度是O(n2*(log2(n)2)),而且需要两个求最大最小,所以会爆空间,大概也会T,233。

所以这个时候发现n还是蛮重要的,dp[i][j]表示以点(i,j)为左上角,(i+(1<<(log2(n)-1)),j+(1<<(log2(n)-1)))为右下角的矩形区域内的最值。

如果不好理解可以在开一维k,即dp[i][j][k]表示以点(i,j)为左上角,(i+(1<<(k-1)),j+(1<<(k-1)))为右下角的矩形区域最值。

这样预处理之后枚举左上角,可以做到O(1)查询区间最值。

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
const int inf = 2e9;
int dpM[maxn][maxn];
int dpm[maxn][maxn];
int logk;
int query(int x, int y, int k) {
int w = k - ( << logk);
int Max = max(max(dpM[x][y], dpM[x + w][y + w]), max(dpM[x + w][y], dpM[x][y + w]));
int Min = min(min(dpm[x][y], dpm[x + w][y + w]), min(dpm[x + w][y], dpm[x][y + w]));
return Max - Min;
}
int main() {
int n, m, k, x;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j) {
scanf("%d", &x);
dpM[i][j] = dpm[i][j] = x;
}
logk = log2(k);
for (int t = ; t < logk; t++) {
for (int i = ; i + ( << t) <= n; i++) {
for (int j = ; j + ( << t) <= m; j++) {
dpM[i][j] = max(max(dpM[i][j], dpM[i + ( << t)][j + ( << t)]), max(dpM[i + ( << t)][j], dpM[i][j + ( << t)]));
dpm[i][j] = min(min(dpm[i][j], dpm[i + ( << t)][j + ( << t)]), min(dpm[i + ( << t)][j], dpm[i][j + ( << t)]));
}
}
}
int ans = inf;
for (int i = ; i <= n - k+; i++) {
for (int j = ; j <= m - k+; j++) {
ans = min(ans, query(i, j, k));
//cout << query(i, j, k) << " ";
}
}
printf("%d\n", ans);
}