思路与算法

建立二维SparseTable，t[a][b][i,j]表示从(i,j)出发高2^a宽2^b的最大值，先横向合并再纵向合并。查询取不超过高宽的最大二次幂，用四个角对齐的块覆盖整个矩形，四值最大即可。

正确性说明

二维表按两半归纳精确。查询四块的并集覆盖所有目标格且不越界，块可重叠，而max具有幂等性，重复覆盖不会改变结果，所以四值最大就是矩形最大值。

复杂度

分配并清空O(NMlogNlogM)，建表同阶，K次查询O(K)，总O(NMlogNlogM+K)时间；表空间O(NMlogNlogM)，输入输出可逐条处理。

易错点

单行、单列和单格都要支持，计算log的参数始终正。元素可达2^31-1；百万行合法输出可能超过4MiB，本批验证器仅按预期字节扩大捕获，原题时间内存及原生判题保持原限。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    int K = 31 - __builtin_clz(n), L = 31 - __builtin_clz(m);
    vector<vector<vector<int>>> t(K + 1, vector<vector<int>>(L + 1, vector<int>(n * m)));
    for (int &x : t[0][0])
        cin >> x;
    for (int b = 1; b <= L; b++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j + (1 << b) <= m; j++)
                t[0][b][i * m + j] =
                    max(t[0][b - 1][i * m + j], t[0][b - 1][i * m + j + (1 << (b - 1))]);
    for (int a = 1; a <= K; a++)
        for (int b = 0; b <= L; b++)
            for (int i = 0; i + (1 << a) <= n; i++)
                for (int j = 0; j + (1 << b) <= m; j++)
                    t[a][b][i * m + j] =
                        max(t[a - 1][b][i * m + j], t[a - 1][b][(i + (1 << (a - 1))) * m + j]);
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a;
        --b;
        --c;
        --d;
        int x = 31 - __builtin_clz(c - a + 1), y = 31 - __builtin_clz(d - b + 1),
            i = c - (1 << x) + 1, j = d - (1 << y) + 1;
        cout << max(max(t[x][y][a * m + b], t[x][y][i * m + b]),
                    max(t[x][y][a * m + j], t[x][y][i * m + j]))
             << '\n';
    }
}