概要

グリッド上にマンハッタン距離で定義されるダイヤモンド型の範囲を順にペイントしていき、各回で新たにペイントされたマスのスコア合計を求める問題です。各行ごとに「未ペイント区間」を管理することで効率的に解きます。

考察

素朴なアプローチの問題点:
各クエリで対象マスを1つずつ確認すると、1回のペイントで最大 \(O(D^2)\) マスを走査する必要があり、TLEになります。

重要な観察:

1. マンハッタン距離 \(D\) 以下の領域を行ごとに見ると、行 \(i\) におけるペイント対象は連続した列の区間 \([\max(1, C - \text{rem}),\ \min(W, C + \text{rem})]\)（ただし \(\text{rem} = D - |i - R|\)）になります。
2. 各行について「まだペイントされていない区間」を管理しておけば、ペイント対象区間との重なり部分だけがスコアに寄与します。
3. 一度ペイントされたマスは二度とスコアに寄与しないため、全クエリを通じて「区間を削除する操作」の総回数は有限です（各マスは高々1回削除される）。

制約 \(H \times Q \leq 4 \times 10^6\) の意味:
全クエリで訪問する行数の合計が高々 \(4 \times 10^6\) であることが保証されており、行ごとの処理が高速ならば間に合います。

アルゴリズム

1. 前処理: 各行について列方向の累積和 prefix[i][j] を計算しておく。これにより任意の行の区間 \([l, r]\) のスコア合計を \(O(1)\) で求められる。

2. 未ペイント区間の管理: 各行 \(i\) に対して、set<pair<int,int>> で未ペイントの列区間の集合を管理する。初期状態では各行に区間 \([1, W]\) が1つだけ入っている。

3. 各クエリの処理:

   • ペイント対象の行範囲 \([\max(1, R-D),\ \min(H, R+D)]\) を走査する。
   • 各行 \(i\) について、ペイント対象の列範囲 \([l, r]\) を計算する。
   • その行の未ペイント区間集合から \([l, r]\) と重なる区間を探索する。
   • 重なった部分のスコアを累積和で計算し、区間を適切に更新する：
     • 完全に含まれる区間 → 削除
     • 部分的に重なる区間 → 残り部分を再挿入
     • ペイント範囲を完全に含む区間 → 左右に分割

4. スコアを出力する。

計算量

• 時間計算量: \(O(H \times W + H \times Q \times \log W)\)

  • \(H \times W\)：入力読み込みと累積和の構築
  • 全クエリでの行訪問回数は合計 \(O(H \times Q)\) 回で、各行訪問時に set 操作が \(O(\log W)\)
  • 区間の削除回数は全体で \(O(H \times W)\)（各マスは高々1回削除されるため）を超えない

• 空間計算量: \(O(H \times W)\)

  • 累積和配列と未ペイント区間の管理

実装のポイント

• 累積和は行ごとに持つ: 2次元累積和ではなく、各行の1次元累積和で十分。行 \(i\) の列 \([l, r]\) の合計は prefix[i][r] - prefix[i][l-1] で求まる。

• lower_bound の使い方に注意: ペイント範囲 \([l, r]\) と重なる最初の区間を見つけるために、lower_bound({l, 0}) で検索した後、一つ前の区間も確認する必要がある（その区間の右端が \(l\) 以上なら重なっている）。

• 区間分割時のループ脱出: ペイント範囲が区間の内側に完全に含まれる場合（左右に分割する場合）、新たに挿入した右側の区間を再走査しないよう break する。

• set の erase とイテレータの無効化: erase 前に次のイテレータを取得しておく（++it してから erase(to_erase)）。

  ソースコード

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

この解説は claude4.6opus-thinking によって生成されました。