题目大意：有一个$a\times b$的矩阵，求一个$n\times n$的矩阵，使该区域中的极差最小。
题解：二维$ST$表，每一个点试一下是不是左上角就行了
卡点：1.用了一份考试时候写的二维$ST$表，是矩阵的，然后$MLE$
2.改了一下，$i,k$狂写错
C++ Code：
#include <cstdio>
#define maxn 1005
int S[maxn][maxn][11], M[maxn][maxn][11];
int n, m, p, K, P;
int LG[maxn], pw[maxn];
inline int max(int a, int b) {return a > b ? a : b;}
inline int min(int a, int b) {return a < b ? a : b;}
inline int getS(int a, int b) {
int c = a + p, d = b + p;
int l = max(S[a][b][K], S[c - P][b][K]),
r = max(S[a][d - P][K], S[c - P][d - P][K]);
return max(l, r);
}
inline int getM(int a, int b) {
int c = a + p, d = b + p;
int l = min(M[a][b][K], M[c - P][b][K]),
r = min(M[a][d - P][K], M[c - P][d - P][K]);
return min(l, r);
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for (register int i = 1; i <= n; i++) {
for (register int j = 1; j <= m; j++) scanf("%d", &S[i][j][0]), M[i][j][0] = S[i][j][0];
}
LG[0] = -1; for (int i = 1; i < maxn; i++) LG[i] = LG[i >> 1] + 1; K = LG[p];
pw[0] = 1; for (int i = 1; i < 100; i++) pw[i] = pw[i - 1] * 2ll % 20040826; P = pw[K];
for (register int k = 1; k < 11; k++) {
for (register int i = 1; i <= n; i++) {
for (register int j = 1; j <= m; j++) {
S[i][j][k] = max(max(S[i][j][k - 1], S[i][min(m, j + pw[k - 1])][k - 1]),
max(S[min(n, i + pw[k - 1])][j][k - 1], S[min(n, i + pw[k - 1])][min(m, j + pw[k - 1])][k - 1]));
M[i][j][k] = min(min(M[i][j][k - 1], M[i][min(m, j + pw[k - 1])][k - 1]),
min(M[min(n, i + pw[k - 1])][j][k - 1], M[min(n, i + pw[k - 1])][min(m, j + pw[k - 1])][k - 1]));
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n - p + 1; i++) {
for (int j = 1; j <= m - p + 1; j++) {
ans = min(ans, getS(i, j) - getM(i, j));
}
}
printf("%d\n", ans);
return 0;
}
原文：https://www.cnblogs.com/Memory-of-winter/p/9742032.html