题意

给定一个 的高度矩阵。有 次询问，每次给出一个中心点 和曼哈顿距离 。要求在所有与 曼哈顿距离恰好为 的点中，找出高度最大的点并输出其高度。若不存在距离恰好为 的点则输出 。

题解

直接枚举与中心点距离为 的所有点显然会超时。因此我们需要考虑曼哈顿距离边界的性质。

Hint: 在二维平面中，与定点 曼哈顿距离恰好为 的所有点构成一个菱形边框（旋转了 的正方形）。 这个边框可以自然地拆分为四条斜率分别为 和 的线段。

我们可以根据绝对值的展开，将菱形边界拆解为四条线段：

  1. 第一象限方向：
  2. 第四象限方向：
  3. 第二象限方向：
  4. 第三象限方向：

可以发现，这四条线段上的点，要么位于同一条主对角线（）上，要么位于同一条副对角线（）上。 因此，我们可以提前把矩阵按主对角线和副对角线分别提取出来，拼接成若干个一维连续的数组。

为了应对 次询问，我们需要快速求出某条对角线上任意给定横坐标 范围内的最大高度。由于矩阵的高度信息是静态的，这就转化为了一个经典的静态区间最值查询问题（RMQ）。 我们可以对拼接好的一维数组建立 ST 表（Sparse Table） 或者线段树。由于询问次数 较大，且仅有查询没有修改，使用能在 复杂度内返回查询结果的 ST 表是最优选择。

每次询问时，计算出对应的四条对角线编号，并根据 与 的大小关系计算出在这四条对角线上的 的有效区间 。最后在这四个区间内分别通过 ST 表查询最大值并取全局最大值即可。需要注意判断 过大导致线段完全在矩阵外的情况。

复杂度

  • 时间复杂度:
  • 空间复杂度:

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 600005;
const int INF = 2e9 + 5;
int stS[20][N], stD[20][N], lg2[N];

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(n * m);
    for (int i = 0; i < n * m; ++i) cin >> a[i];

    vector<int> vS, vD;
    vector<int> posS(n + m + 1), stS(n + m + 1);
    vector<int> posD(n + m + 1), stD(n + m + 1);

    for (int s = 2; s <= n + m; ++s) {
        int r_min = max(1, s - m), r_max = min(n, s - 1);
        posS[s] = vS.size();
        stS[s] = r_min;
        for (int r = r_min; r <= r_max; ++r) {
            vS.push_back(a[(r - 1) * m + s - r - 1]);
        }
    }

    for (int d = 1 - m; d <= n - 1; ++d) {
        int r_min = max(1, 1 + d), r_max = min(n, m + d);
        posD[d + m] = vD.size();
        stD[d + m] = r_min;
        for (int r = r_min; r <= r_max; ++r) {
            vD.push_back(a[(r - 1) * m + r - d - 1]);
        }
    }

    for (int i = 0; i < vS.size(); ++i) stS[0][i] = vS[i];
    for (int j = 1; (1 << j) <= vS.size(); ++j)
        for (int i = 0; i + (1 << j) <= vS.size(); ++i)
            stS[j][i] = max(stS[j - 1][i], stS[j - 1][i + (1 << (j - 1))]);

    for (int i = 0; i < vD.size(); ++i) stD[0][i] = vD[i];
    for (int j = 1; (1 << j) <= vD.size(); ++j)
        for (int i = 0; i + (1 << j) <= vD.size(); ++i)
            stD[j][i] = max(stD[j - 1][i], stD[j - 1][i + (1 << (j - 1))]);

    auto query_st = [&](int st[20][N], int L, int R) {
        if (L > R) return -INF;
        int k = lg2[R - L + 1];
        return max(st[k][L], st[k][R - (1 << k) + 1]);
    };

    while (q--) {
        ll x, y, k;
        cin >> x >> y >> k;
        int ans = -INF;

        ll S1 = x + y + k;
        if (S1 >= 2 && S1 <= n + m) {
            int r1 = max(x, S1 - m), r2 = min(1LL * n, S1 - y);
            ans = max(ans, query_st(stS, posS[S1] + r1 - stS[S1], posS[S1] + r2 - stS[S1]));
        }
        ll D1 = x - y + k;
        if (D1 + m >= 1 && D1 + m <= n + m - 1) {
            int r1 = max(x, D1 + 1), r2 = min(1LL * n, D1 + y - 1);
            ans = max(ans, query_st(stD, posD[D1 + m] + r1 - stD[D1 + m], posD[D1 + m] + r2 - stD[D1 + m]));
        }
        ll D2 = x - y - k;
        if (D2 + m >= 1 && D2 + m <= n + m - 1) {
            int r1 = max(1LL, D2 + y), r2 = min(x - 1, D2 + m);
            ans = max(ans, query_st(stD, posD[D2 + m] + r1 - stD[D2 + m], posD[D2 + m] + r2 - stD[D2 + m]));
        }
        ll S2 = x + y - k;
        if (S2 >= 2 && S2 <= n + m) {
            int r1 = max(1LL, S2 - y + 1), r2 = min(x - 1, S2 - 1);
            ans = max(ans, query_st(stS, posS[S2] + r1 - stS[S2], posS[S2] + r2 - stS[S2]));
        }

        cout << (ans <= -INF + 10 ? -1 : ans) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    for (int i = 2; i < MAXN; ++i) lg2[i] = lg2[i / 2] + 1;
    int t; cin >> t;
    while (t--) solve();
}