题解 | 再临艾弗埃恩地

赛时想到了一个比较简单的方法，成功通过。

如果在每次询问时直接枚举整个矩阵，显然会超时，因此需要优化。

枚举一维坐标

由于每次只需要枚举与 (x, y) 曼哈顿距离为 k 的点，不需要枚举所有点，因此可以枚举 x'：

对应的 y' 有两个：
y1' = y + (k - |x' - x|)
y2' = y - (k - |x' - x|) 此时单次查询的复杂度为 $O(n)$ ，总复杂度 $O(n \cdot q)$ 。
已知 $n \le 3 \times 10^5$ ， $q \le 5 \times 10^5$ ，仍然超时。
同理，枚举 y' 也会得到 $O(m \cdot q)$ ，同样不可行。

枚举较小维度

考虑枚举 $n$ 和 $m$ 中的较小值，复杂度为 $O(\min(n, m) \cdot q)$ 。
表面上看仍然很大，但题目限制 $n \cdot m \le 6 \times 10^5$ ，因此：

\min(n, m) \le \sqrt{n \cdot m} \approx \sqrt{6 \times 10^5} \approx 775

于是复杂度上界为：

O(\min(n, m) \cdot q) \le O(\sqrt{n \cdot m} \cdot q) \approx 775 \times 5 \times 10^5 \approx 3.9 \times 10^8

这个复杂度在极限情况下比较临界，赛时耗时约 2000ms 通过。

参考代码

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> h(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> h[i][j];

    while (q--) {
        int x, y, k;
        cin >> x >> y >> k;
        vector<int> res;

        if (n > m) {
            // 枚举列
            for (int j = 1; j <= m; j++) {
                int dy = abs(j - y);
                int dx = k - dy;
                if (dx >= 0) {
                    int x1 = x + dx;
                    if (x1 >= 1 && x1 <= n) res.push_back(h[x1][j]);
                    x1 = x - dx;
                    if (x1 >= 1 && x1 <= n) res.push_back(h[x1][j]);
                }
            }
        } else {
            // 枚举行
            for (int i = 1; i <= n; i++) {
                int dx = abs(i - x);
                int dy = k - dx;
                if (dy >= 0) {
                    int y1 = y + dy;
                    if (y1 >= 1 && y1 <= m) res.push_back(h[i][y1]);
                    y1 = y - dy;
                    if (y1 >= 1 && y1 <= m) res.push_back(h[i][y1]);
                }
            }
        }

        if (res.empty()) {
            cout << -1 << '\n';
        } else {
            int ans = -INF;
            for (int t : res) ans = max(ans, t);
            cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}