概要

各ペイントはマンハッタン距離 \(D_t\) 以下のひし形領域を塗ります。
各回について「まだ塗られていないマス」だけのスコア合計を求めます。

考察

ペイント範囲はマンハッタン距離で決まるため、形はひし形になります。

中心が \((R, C)\)、距離が \(D\) のとき、ある行 \(i\) に注目すると、

\[ |i - R| + |j - C| \leq D \]

より、

\[ |j - C| \leq D - |i - R| \]

となります。

したがって、行 \(i\) で塗られる列の範囲は連続区間になります。

具体的には、

\[ \text{rem} = D - |i - R| \]

とすると、

\[ C - \text{rem} \leq j \leq C + \text{rem} \]

です。

ただし、キャンバス外にはみ出す部分は無視するので、実際には

\[ L = \max(1, C - \text{rem}) \]

\[ R = \min(W, C + \text{rem}) \]

となります。

---

素朴に各ペイントについて、範囲内のすべてのマスを調べると、同じマスを何度も確認することになります。

例えば、すでに塗られた大きな領域に何度もペイントが重なると、毎回その領域全体を走査してしまい、TLE になります。

そこで重要なのは、

一度塗られたマスは、以降は二度とスコアに関係しない

という点です。

つまり、各マスは「初めて塗られたとき」だけ処理すれば十分です。

これを実現するために、各行ごとに「次にまだ塗られていない列」を高速に探せるデータ構造を用意します。

これは Union-Find のような「次の未処理要素を管理するテクニック」で実現できます。

アルゴリズム

各行について、列方向に Union-Find 風の配列 parent を持ちます。

parent[i][j] は、行 \(i\) において列 \(j\) 以降で次に確認すべき列を表します。

初期状態ではすべて未ペイントなので、

\[ parent[i][j] = j \]

です。

あるマス \((i, j)\) を塗ったら、そのマスは今後見る必要がありません。
そのため、

\[ parent[i][j] = find(i, j + 1) \]

として、次回以降は列 \(j\) を飛ばして列 \(j+1\) 以降を見るようにします。

---

各クエリでは、まず塗られる行の範囲を求めます。

\[ \max(1, R - D) \leq i \leq \min(H, R + D) \]

各行 \(i\) について、塗られる列区間 \([L, RR]\) を求めます。

その後、

1. find(i, L) で、区間内の最初の未ペイント列を探す
2. その列が \(RR\) 以下なら、そのマスを新たに塗る
3. スコアを答えに加算する
4. その列を Union-Find で「削除」する
5. 次の未ペイント列へ進む

という処理を繰り返します。

例えば、ある行で列 \(2,3,4,5\) を塗りたいとします。
すでに列 \(3,4\) が塗られていれば、find によってそれらを飛ばし、列 \(2,5\) だけを処理できます。

これにより、各マスは高々 1 回しかスコア加算されません。

計算量

• 時間計算量: \(O((HW + HQ)\alpha(W))\)
• 空間計算量: \(O(HW)\)

ここで \(\alpha(W)\) はアッカーマン関数の逆関数で、実用上はほぼ定数です。

各クエリでは、塗られる可能性のある行を走査します。
その合計は制約より \(O(HQ)\) です。

また、実際に新たに塗られるマスは全体で高々 \(HW\) 個なので、列方向の処理回数の合計は \(O(HW)\) です。

実装のポイント

parent は各行ごとに用意します。

列 \(W+1\) を番兵として使うことで、行の右端を超えた場合も自然に処理できます。

parent[i][W + 1] = W + 1;

塗る処理では、次のようにします。

int j = find(i, L);
while (j <= RR) {
    ans += A[i][j];
    parent[i][j] = find(i, j + 1);
    j = find(i, j);
}

parent[i][j] = find(i, j + 1) によって、列 \(j\) は今後スキップされます。

また、答えはスコアの合計なので、int ではなく long long を使う必要があります。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    vector<vector<long long>> A(H + 1, vector<long long>(W + 2));
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> A[i][j];
        }
    }

    vector<vector<int>> parent(H + 1, vector<int>(W + 2));
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W + 1; j++) {
            parent[i][j] = j;
        }
    }

    auto find = [&](auto&& self, int r, int x) -> int {
        if (parent[r][x] == x) return x;
        return parent[r][x] = self(self, r, parent[r][x]);
    };

    int Q;
    cin >> Q;

    while (Q--) {
        int R, C, D;
        cin >> R >> C >> D;

        long long ans = 0;

        int top = max(1, R - D);
        int bottom = min(H, R + D);

        for (int i = top; i <= bottom; i++) {
            int rem = D - abs(i - R);
            int L = max(1, C - rem);
            int RR = min(W, C + rem);

            int j = find(find, i, L);
            while (j <= RR) {
                ans += A[i][j];
                parent[i][j] = find(find, i, j + 1);
                j = find(find, i, j);
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。