题目链接：https://loj.ac/problem/10182

题目链接：https://www.luogu.com.cn/problem/P2216

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

做法

正解是单调队列，然而我太菜了，有时间再去研究单调队列做法。

二维st表预处理，复杂度$O(ablogn)$，n大的话$a$和$b$都跑不满，算算时间复杂度可以过

查询的时候O（1）查询就好了

预处理&查询

• $st[i][j][k]$表示以$(i, j)$为左上角的长度为$2^k$的正方形的最值
• 转移的时候每一个大的正方形可以由四个小正方形拼起来，查询的时候用四个$log(n)$的正方形覆盖起来

也没什么细节，这个做法比较简单比较好想。

代码

#include 
#include 
#include 
#include 
using namespace std;
inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int maxN = 1005;
int a, b, n, stmax[maxN][maxN][11], stmin[maxN][maxN][11], K;
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 Qmax(int i, int j) {
    return max(max(stmax[i][j][K], stmax[i + n - (1 << K)][j][K]),
               max(stmax[i][j + n - (1 << K)][K], stmax[i + n - (1 << K)][j + n - (1 << K)][K]));
}
inline int Qmin(int i, int j) {
    return min(min(stmin[i][j][K], stmin[i + n - (1 << K)][j][K]),
               min(stmin[i][j + n - (1 << K)][K], stmin[i + n - (1 << K)][j + n - (1 << K)][K]));
}
int main() {
    a = read(), b = read(), n = read();
    for (int i = 1; i <= a; ++i)
        for (int j = 1; j <= b; ++j) stmin[i][j][0] = read(), stmax[i][j][0] = stmin[i][j][0];
    K = log2(n);
    for (int k = 1; k <= K; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= a; ++i) {
            for (int j = 1; j + (1 << k) - 1 <= b; ++j) {
                stmax[i][j][k] = max(stmax[i][j][k - 1], stmax[i + (1 << (k - 1))][j][k - 1]);
                stmax[i][j][k] = max(stmax[i][j][k], stmax[i][j + (1 << (k - 1))][k - 1]);
                stmax[i][j][k] = max(stmax[i][j][k], stmax[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1]);

                stmin[i][j][k] = min(stmin[i][j][k - 1], stmin[i + (1 << (k - 1))][j][k - 1]);
                stmin[i][j][k] = min(stmin[i][j][k], stmin[i][j + (1 << (k - 1))][k - 1]);
                stmin[i][j][k] = min(stmin[i][j][k], stmin[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1]);
            }
        }
    }
    int ans = 2e9;
    for (int i = 1; i <= a - n + 1; ++i) {
        for (int j = 1; j <= b - n + 1; ++j) {
            ans = min(ans, Qmax(i, j) - Qmin(i, j));
        }
    }
    cout << ans << '\n';
    return 0;
}