Overview

This problem involves sequentially painting diamond-shaped regions defined by Manhattan distance on a grid, and computing the total score of newly painted cells each time. It is solved efficiently by managing “unpainted intervals” for each row.

Analysis

Problem with the naive approach:
If we check each target cell one by one per query, we would need to scan up to \(O(D^2)\) cells per paint operation, resulting in TLE.

Key observations:

1. When viewing the region within Manhattan distance \(D\) row by row, the paint target for row \(i\) is a contiguous interval of columns \([\max(1, C - \text{rem}),\ \min(W, C + \text{rem})]\) (where \(\text{rem} = D - |i - R|\)).
2. If we maintain the “not yet painted intervals” for each row, only the overlapping portions with the paint target interval contribute to the score.
3. Since a cell that has already been painted never contributes to the score again, the total number of “interval deletion operations” across all queries is finite (each cell is deleted at most once).

Meaning of the constraint \(H \times Q \leq 4 \times 10^6\):
It is guaranteed that the total number of rows visited across all queries is at most \(4 \times 10^6\), so as long as the per-row processing is fast, the solution will fit within the time limit.

Algorithm

1. Preprocessing: Compute the column-wise prefix sums prefix[i][j] for each row. This allows computing the total score for any interval \([l, r]\) in a given row in \(O(1)\).

2. Managing unpainted intervals: For each row \(i\), maintain a set of unpainted column intervals using set<pair<int,int>>. Initially, each row contains a single interval \([1, W]\).

3. Processing each query:

   • Scan the range of target rows \([\max(1, R-D),\ \min(H, R+D)]\).
   • For each row \(i\), compute the target column range \([l, r]\).
   • Search the unpainted interval set for that row to find intervals overlapping with \([l, r]\).
   • Compute the score of the overlapping portions using prefix sums, and update the intervals accordingly:
     • Intervals completely contained → delete
     • Intervals partially overlapping → reinsert the remaining portion
     • Intervals that completely contain the paint range → split into left and right parts

4. Output the score.

Complexity

• Time complexity: \(O(H \times W + H \times Q \times \log W)\)

  • \(H \times W\): reading input and building prefix sums
  • The total number of row visits across all queries is \(O(H \times Q)\), and each row visit involves set operations costing \(O(\log W)\)
  • The total number of interval deletions does not exceed \(O(H \times W)\) (since each cell is deleted at most once)

• Space complexity: \(O(H \times W)\)

  • For the prefix sum arrays and unpainted interval management

Implementation Notes

• Prefix sums are maintained per row: Instead of 2D prefix sums, 1D prefix sums for each row suffice. The sum of columns \([l, r]\) in row \(i\) is obtained as prefix[i][r] - prefix[i][l-1].

• Be careful with the use of lower_bound: To find the first interval overlapping with the paint range \([l, r]\), after searching with lower_bound({l, 0}), you also need to check the previous interval (it overlaps if its right endpoint is at least \(l\)).

• Breaking out of the loop during interval splitting: When the paint range is completely contained inside an interval (i.e., when splitting into left and right parts), use break to avoid re-scanning the newly inserted right interval.

• set’s erase and iterator invalidation: Obtain the next iterator before erasing (advance with ++it and then call erase(to_erase)).

  Source Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int H, W;
    cin >> H >> W;
    
    vector<vector<long long>> prefix(H + 1, vector<long long>(W + 1, 0));
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            long long a;
            cin >> a;
            prefix[i][j] = prefix[i][j-1] + a;
        }
    }
    
    vector<set<pair<int,int>>> unpainted(H + 1);
    for (int i = 1; i <= H; i++) {
        unpainted[i].insert({1, W});
    }
    
    int Q;
    cin >> Q;
    
    while (Q--) {
        int R, C, D;
        cin >> R >> C >> D;
        
        long long score = 0;
        
        int ilow = max(1, R - D), ihigh = min(H, R + D);
        for (int i = ilow; i <= ihigh; i++) {
            int rem = D - abs(i - R);
            int l = max(1, C - rem);
            int r = min(W, C + rem);
            
            auto& s = unpainted[i];
            
            auto it = s.lower_bound({l, 0});
            if (it != s.begin()) {
                --it;
                if (it->second < l) ++it;
            }
            
            while (it != s.end() && it->first <= r) {
                int a = it->first, b = it->second;
                int ol = max(a, l), orr = min(b, r);
                score += prefix[i][orr] - prefix[i][ol - 1];
                
                auto to_erase = it;
                ++it;
                
                if (a >= l && b <= r) {
                    s.erase(to_erase);
                } else if (a < l && b > r) {
                    s.erase(to_erase);
                    s.insert({a, l - 1});
                    s.insert({r + 1, b});
                    break;
                } else if (a < l) {
                    s.erase(to_erase);
                    s.insert({a, l - 1});
                } else {
                    s.erase(to_erase);
                    s.insert({r + 1, b});
                    break;
                }
            }
        }
        
        cout << score << '\n';
    }
    
    return 0;
}

This editorial was generated by claude4.6opus-thinking.