Overview

Each paint operation colors a diamond-shaped region within Manhattan distance \(D_t\).
For each operation, we need to find the total score of only the “not yet painted cells.”

Analysis

Since the paint range is determined by Manhattan distance, the shape is a diamond.

When the center is \((R, C)\) and the distance is \(D\), focusing on a particular row \(i\):

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

gives us:

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

Therefore, the range of columns painted in row \(i\) forms a contiguous interval.

Specifically, if we let:

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

then:

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

However, since we ignore parts that extend outside the canvas, the actual range is:

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

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

---

If we naively check all cells within the range for each paint operation, we end up examining the same cells multiple times.

For example, if paint operations repeatedly overlap with an already painted large region, we would scan that entire region each time, resulting in TLE.

The key observation is:

Once a cell is painted, it never contributes to the score again.

In other words, it is sufficient to process each cell only “when it is painted for the first time.”

To achieve this, we prepare a data structure for each row that can quickly find the “next unpainted column.”

This can be implemented using a technique similar to Union-Find for “managing the next unprocessed element.”

Algorithm

For each row, we maintain a Union-Find-like array parent in the column direction.

parent[i][j] represents the next column to check at or after column \(j\) in row \(i\).

In the initial state, all cells are unpainted, so:

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

Once a cell \((i, j)\) is painted, there is no need to look at it again.
Therefore, we set:

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

so that from the next time onward, column \(j\) is skipped and we look at column \(j+1\) and beyond.

---

For each query, we first determine the range of rows to be painted:

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

For each row \(i\), we compute the column interval \([L, RR]\) to be painted.

Then, we repeat the following process:

1. Use find(i, L) to find the first unpainted column within the interval
2. If that column is \(\leq RR\), paint that cell as newly painted
3. Add the score to the answer
4. “Delete” that column using Union-Find
5. Move to the next unpainted column

For example, suppose we want to paint columns \(2, 3, 4, 5\) in some row.
If columns \(3, 4\) are already painted, find skips over them, and we only process columns \(2, 5\).

This ensures that each cell contributes to the score at most once.

Complexity

• Time complexity: \(O((HW + HQ)\alpha(W))\)
• Space complexity: \(O(HW)\)

Here, \(\alpha(W)\) is the inverse Ackermann function, which is practically constant.

For each query, we scan the rows that could potentially be painted.
The total of this is \(O(HQ)\) by the constraints.

Also, since the total number of newly painted cells across all operations is at most \(HW\), the total number of column-direction operations is \(O(HW)\).

Implementation Details

parent is prepared for each row.

By using column \(W+1\) as a sentinel, we can naturally handle the case where we go beyond the right edge of the row.

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

The painting process is done as follows:

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

By setting parent[i][j] = find(i, j + 1), column \(j\) will be skipped from now on.

Also, since the answer is a sum of scores, you need to use long long instead of int.

Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.