概要

\(H \times W\) のグリッド上で、道路工事（長方形領域の空き地を道路に変更）を \(Q\) 回行い、各工事の直後に「道路に面している建物の総数」を求める問題です。

考察

1. 道路に面する条件の変化

建物が「道路に面している」状態になるのは、以下のいずれかの場合です。 - 初期状態で、隣接するマスに道路がある。 - 道路工事によって、隣接するマスが空き地から道路に変わる。

一度道路に面した建物は、その後の工事で道路が増えても「道路に面している」状態のままです。したがって、「新しく道路に面することになった建物」を順次カウントしていくというアプローチが有効です。

2. 工事の影響範囲

各工事では、長方形領域 \([U, D] \times [L, R]\) 内の空き地がすべて道路になります。このとき、新しく道路に面する可能性がある建物は、この長方形領域のすぐ外側（上下左右）に隣接している建物だけです。

具体的には、以下の 4 つの範囲にある建物を調べれば十分です。 1. 上端の 1 行上：行 \(U-1\)、列 \(L \sim R\) 2. 下端の 1 行下：行 \(D+1\)、列 \(L \sim R\) 3. 左端の 1 列左：列 \(L-1\)、行 \(U \sim D\) 4. 右端の 1 列右：列 \(R+1\)、行 \(U \sim D\)

問題文の制約に「工事範囲内に建物は含まれない」とあるため、長方形の内部を気にする必要はありません。

3. 計算量の見積もり

素朴に毎クエリ全マスを走査すると \(O(Q \times HW)\) となり間に合いません。 しかし、上記の通り「長方形の境界」のみをチェックする場合、各クエリでの処理は長方形の周囲の長さに比例します。 制約を見ると、\(\sum (\text{周囲の長さ}) \leq 5 \times 10^6\) となっており、この計算量なら十分に間に合うことがわかります。

アルゴリズム

1. 初期状態のカウント:
   • 全マスを走査し、建物 ‘B’ を見つけたら上下左右に ‘R’ があるか確認します。
   • 道路に面していれば、フラグ is_facing[i][j] を真にし、現在のカウント current_count を増やします。
2. クエリ処理:
   • 各工事の長方形領域の 4 辺の外側を走査します。
   • マス \((i, j)\) が建物 ‘B’ であり、かつ is_facing[i][j] が偽である場合：
     • is_facing[i][j] を真に更新し、current_count を 1 増やします。
   • 各クエリの最後に current_count を出力します。

計算量

• 時間計算量: \(O(HW + \sum_{k=1}^{Q} (\text{Perimeter}_k))\)
  • 初期走査に \(O(HW)\)、各クエリの境界走査に \(O(D_k - U_k + R_k - L_k)\) かかります。制約より、これらは合計で約 \(7 \times 10^6\) 程度の操作回数となり、制限時間内に収まります。
• 空間計算量: \(O(HW)\)
  • グリッドの情報を保持する \(S\) と、建物ごとの状態を保持する is_facing 配列（または vector）に \(O(HW)\) のメモリを使用します。

実装のポイント

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

• 1次元配列での管理: 2次元配列 is_facing[H][W] を使う代わりに、is_facing[i * W + j] のように1次元配列で管理することで、メモリ効率やアクセス速度を向上させることができます。

• 範囲外アクセスの防止: 長方形の境界をチェックする際、その境界がグリッドの端（行 0 や \(H-1\) など）を越えないように if 文で境界チェックを行う必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * Problem: City Planning and Road Maintenance
 * We need to count how many buildings 'B' are facing at least one road 'R'.
 * Initially, some buildings might already face roads.
 * Q road construction queries change all 'E' cells in a rectangle [U, D] x [L, R] to 'R'.
 * Buildings are never in the construction region.
 * We need to output the count of buildings facing a road after each query.
 * 
 * Logic:
 * 1. Identify which buildings initially face a road by checking their 4 neighbors.
 * 2. For each query, all cells in the rectangle [U, D] x [L, R] become 'R'.
 * 3. Any building outside the region that is adjacent to any cell inside the region will now face a road.
 * 4. The buildings adjacent to the rectangle are on its four immediate boundaries:
 *    - Row U-1, columns L to R
 *    - Row D+1, columns L to R
 *    - Column L-1, rows U to D
 *    - Column R+1, rows U to D
 * 5. Update the facing status of these buildings and the total count if they weren't already facing a road.
 * 6. Time complexity: O(HW + Sum of Perimeters), which fits within the limits.
 *    Initial check: O(HW), Query processing: O(Sum of (2*(D-U+1) + 2*(R-L+1))).
 *    Given HW <= 2e6 and Sum of Perimeters <= 5e6, total operations are ~7e6.
 */

int main() {
    // Fast I/O for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // Grid storage: use a vector of strings. HW <= 2e6, so this is memory-efficient.
    vector<string> S(H);
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }

    // is_facing[i*W + j] tracks if building (i, j) is facing a road.
    // Using a 1D vector to handle the grid. vector<char> uses 1 byte per element.
    vector<char> is_facing((long long)H * W, 0);
    long long current_count = 0;

    // Initial check for buildings already facing a road in the initial grid.
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == 'B') {
                bool facing = false;
                // Check 4 cardinal neighbors (Up, Down, Left, Right)
                if (i > 0 && S[i - 1][j] == 'R') facing = true;
                else if (i < H - 1 && S[i + 1][j] == 'R') facing = true;
                else if (j > 0 && S[i][j - 1] == 'R') facing = true;
                else if (j < W - 1 && S[i][j + 1] == 'R') facing = true;
                
                if (facing) {
                    is_facing[(long long)i * W + j] = 1;
                    current_count++;
                }
            }
        }
    }

    // Process Q road construction queries.
    for (int k = 0; k < Q; ++k) {
        int U, D, L, R;
        cin >> U >> D >> L >> R;
        // Convert 1-based coordinates to 0-based.
        --U; --D; --L; --R;

        // Any building adjacent to the query rectangle [U, D] x [L, R]
        // will now face a road. We check the four potential boundary rows/cols.

        // 1. Buildings above the region: row U-1, columns L to R.
        if (U > 0) {
            int i = U - 1;
            for (int j = L; j <= R; ++j) {
                if (S[i][j] == 'B' && !is_facing[(long long)i * W + j]) {
                    is_facing[(long long)i * W + j] = 1;
                    current_count++;
                }
            }
        }
        // 2. Buildings below the region: row D+1, columns L to R.
        if (D < H - 1) {
            int i = D + 1;
            for (int j = L; j <= R; ++j) {
                if (S[i][j] == 'B' && !is_facing[(long long)i * W + j]) {
                    is_facing[(long long)i * W + j] = 1;
                    current_count++;
                }
            }
        }
        // 3. Buildings to the left of the region: column L-1, rows U to D.
        if (L > 0) {
            int j = L - 1;
            for (int i = U; i <= D; ++i) {
                if (S[i][j] == 'B' && !is_facing[(long long)i * W + j]) {
                    is_facing[(long long)i * W + j] = 1;
                    current_count++;
                }
            }
        }
        // 4. Buildings to the right of the region: column R+1, rows U to D.
        if (R < W - 1) {
            int j = R + 1;
            for (int i = U; i <= D; ++i) {
                if (S[i][j] == 'B' && !is_facing[(long long)i * W + j]) {
                    is_facing[(long long)i * W + j] = 1;
                    current_count++;
                }
            }
        }

        // Output the updated count of buildings facing a road after this query.
        cout << current_count << "\n";
    }

    return 0;
}

---

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