概要

\(H \times W\) のグリッド上で、指定された中心 \((R_t, C_t)\) からマンハッタン距離 \(D_t\) 以内のマスを塗りつぶしていくゲームです。各マスにはスコアが設定されており、「初めて塗られたときのみ」そのスコアを獲得できます。各クエリごとに、新たに獲得したスコアの合計を求めます。

考察

1. 素朴なシミュレーションの限界

各クエリに対して、マンハッタン距離 \(D_t\) 以内のマスをすべて走査し、未塗装か判定してスコアを加算する方法が考えられます。しかし、1つのクエリで最大 \(H \times W\) マスが対象になる可能性があり、最悪計算量は \(O(Q \times HW)\) となります。制約の \(H \times W \le 4 \times 10^6\) および \(Q \le 2 \times 10^5\) を考えると、この方法では実行時間制限に間に合いません。

2. マンハッタン距離の範囲を列の区間に分解

マンハッタン距離の条件 \(|i - R_t| + |j - C_t| \leq D_t\) は、行 \(i\) を固定すると、列 \(j\) に関する以下の区間に書き換えられます。 $\(|j - C_t| \leq D_t - |i - R_t|\)\( つまり、行 \)i\( において、列 \)j\( が以下の範囲にあるマスが塗られます。 \)\(C_t - (D_t - |i - R_t|) \leq j \leq C_t + (D_t - |i - R_t|)\)$ この範囲は各行における「連続した区間」です。

3. すでに塗られたマスを高速にスキップする

この問題の肝は、「すでに塗られたマスを二度と走査しない」ことです。 各行について、「次にまだ塗られていない列のインデックス」を管理できれば、効率的に未塗装のマスだけを処理できます。これはUnion-Find (DSU) を用いることで実現可能です。

各行ごとに DSU を用意し、マス \((i, j)\) を塗った直後に、そのマスを \((i, j+1)\) と統合（Union）します。これにより、find(j) を呼び出すだけで、列 \(j\) 以降で次に塗るべきマスの列番号を \(O(\alpha(W))\) で取得できるようになります。

アルゴリズム

1. 初期化:
   • グリッドのスコア \(A_{i,j}\) を保持します（メモリ節約のため 1 次元配列での管理が推奨されます）。
   • 各行 \(1 \leq i \leq H\) に対して、サイズ \(W+2\) の DSU 構造（parent 配列）を用意します。parent[j] = j と初期化します。
2. クエリ処理:
   • 各クエリ \((R_t, C_t, D_t)\) について、影響を受ける行の範囲 \(i \in [\max(1, R_t-D_t), \min(H, R_t+D_t)]\) をループします。
   • 各行 \(i\) について：
     • その行で塗るべき列の範囲 \([c_{start}, c_{end}]\) を計算します。
     • j = find_set(i, c_{start}) により、範囲内の最初の未塗装マスを見つけます。
     • \(j \leq c_{end}\) である限り、以下の処理を繰り返します：

          1. マス $(i, j)$ のスコアを合計に加算。
          2. `parent[i][j] = find_set(i, j + 1)` とすることで、マス $(i, j)$ を「既塗装」としてスキップ対象にする。
          3. 次の未塗装マス `j = find_set(i, j)` へ移動。
       

3. 出力: クエリごとに加算されたスコアを出力します。

計算量

• 時間計算量: \(O(H \times Q + H \times W \times \alpha(W))\)
  • 行のループ回数の合計は、制約より \(\sum \min(H, 2D_t+1) \leq H \times Q \leq 4 \times 10^6\) です。
  • 各マスが「未塗装」として処理されるのは高々 1 回であり、その際の DSU 操作は \(O(\alpha(W))\) です。
  • よって、制限時間内に十分収まります。
• 空間計算量: \(O(H \times W)\)
  • スコア配列と DSU の親ポインタ配列に \(H \times W\) 程度の領域が必要です。

実装のポイント

• メモリ効率: \(H \times W\) が最大 \(4 \times 10^6\) と大きいため、vector<vector<int>> よりも 1 次元配列 vector<int>(H * W) を使用してキャッシュ効率を高め、メモリオーバーヘッドを減らします。

• DSU の簡略化: 今回の DSU は「右隣へ結合する」という特殊なケースであるため、再帰またはループによる経路圧縮のみを実装したシンプルなもので十分高速に動作します。

• 高速な入出力: \(Q\) や \(H \times W\) が大きいため、C++ の場合は cin.tie(NULL); ios_base::sync_with_stdio(false); を使用して入出力を高速化することが必須です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Paint Drop
 * The grid has H rows and W columns, with H * W <= 4,000,000.
 * Q queries are given, each painting a diamond shape with Manhattan distance D.
 * H * Q <= 4,000,000.
 * Each cell is painted only once, and we gain the score of newly painted cells.
 *
 * Complexity:
 * - Total number of row-range operations: sum of min(H, 2*Dt + 1) <= H * Q <= 4,000,000.
 * - Total number of cells painted: H * W <= 4,000,000.
 * - Using Disjoint Set Union (DSU) to skip already painted cells in each row.
 * - Total Time Complexity: O(H * Q + H * W * alpha(W)), which fits within 2 seconds.
 * - Space Complexity: O(H * W) for grid scores and DSU parent pointers.
 */

int main() {
    // Optimize I/O for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    // Use a flat vector to store the grid scores to manage memory efficiently.
    // Scores are up to 10^9, so long long is required for the sum.
    vector<long long> A(static_cast<size_t>(H) * W);
    for (int i = 0; i < H; ++i) {
        size_t row_base = static_cast<size_t>(i) * W;
        for (int j = 0; j < W; ++j) {
            cin >> A[row_base + j];
        }
    }

    int Q;
    if (!(cin >> Q)) return 0;

    // DSU parent array for each row to skip painted cells.
    // parent[i * (W + 2) + j] stores the next unpainted column index in row i.
    // We add +2 to W to safely handle indices from 1 to W+1.
    vector<int> parent(static_cast<size_t>(H) * (W + 2));
    for (int i = 0; i < H; ++i) {
        size_t base = static_cast<size_t>(i) * (W + 2);
        for (int j = 1; j <= W + 1; ++j) {
            parent[base + j] = j;
        }
    }

    // Iterative find_set with path compression for the DSU skip-list.
    // i is the 1-indexed row, j is the 1-indexed column.
    auto find_set = [&](int i, int j) {
        size_t base = static_cast<size_t>(i - 1) * (W + 2);
        int root = j;
        while (parent[base + root] != root) {
            root = parent[base + root];
        }
        int curr = j;
        while (parent[base + curr] != root) {
            int next = parent[base + curr];
            parent[base + curr] = root;
            curr = next;
        }
        return root;
    };

    for (int t = 0; t < Q; ++t) {
        int R, C, D;
        if (!(cin >> R >> C >> D)) break;

        long long total_new_score = 0;
        // Determine the range of rows affected by the Manhattan distance D.
        int r_start = max(1, R - D);
        int r_end = min(H, R + D);

        for (int i = r_start; i <= r_end; ++i) {
            int dist_h = abs(i - R);
            int dist_w = D - dist_h;
            // Range of columns to paint in row i.
            int c_start = max(1, C - dist_w);
            int c_end = min(W, C + dist_w);

            // Use DSU to find the first unpainted column in row i starting from c_start.
            int j = find_set(i, c_start);
            while (j <= c_end) {
                // Cell (i, j) is being painted for the first time.
                total_new_score += A[static_cast<size_t>(i - 1) * W + (j - 1)];
                
                // Mark column j as painted by pointing it to j + 1.
                // This merges the set containing j with the set containing j + 1.
                parent[static_cast<size_t>(i - 1) * (W + 2) + j] = j + 1;
                
                // Move to the next unpainted column in the same row.
                j = find_set(i, j);
            }
        }
        // Output the total score gained from newly painted cells in this query.
        cout << total_new_score << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。