概要

各工事の後に、「上下左右のどこかに道路がある建物」の個数を求めます。
ポイントは、工事によって新たに道路に面する可能性がある建物は、工事長方形のすぐ外側にある建物だけであることです。

考察

工事では、長方形領域内の空き地 E が道路 R になります。
また、工事範囲内には建物 B が含まれないことが保証されています。

したがって、工事後にはその長方形領域内のマスはすべて道路になります。

ここで、ある工事によって新たに道路に面する建物を考えます。

建物が新たに道路に面するためには、その建物の上下左右のどこかに、今回の工事で道路になったマスが存在する必要があります。
今回道路になるマスは長方形の内部にあるので、新たに影響を受ける建物は次の 4 か所だけです。

• 長方形の 1 行上
• 長方形の 1 行下
• 長方形の 1 列左
• 長方形の 1 列右

つまり、長方形の内部全体を調べる必要はありません。

例えば、工事範囲が次の # の部分だとします。

.....
.###.
.###.
.....

新たに道路に面する可能性がある建物は、# の上下左右に隣接する外側のマスだけです。
斜めのマスは道路に面しているとはみなさないため、角の斜め外側は調べません。

素朴に毎回グリッド全体を見直すと \(O(QHW)\) となり、間に合いません。
また、各工事範囲の内部をすべて塗る方法も、長方形の面積が大きい場合に遅くなります。

一方、この問題では工事範囲の周長の合計

\( \sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \)

が小さいことが制約で与えられています。
そのため、各工事で長方形の外周に隣接する部分だけを調べれば高速に処理できます。

アルゴリズム

まず、初期状態で道路に面している建物を数えます。

各建物 B について、上下左右に R があるかを調べます。
道路に面していれば faced[i][j] = true とし、答え ans を 1 増やします。

その後、各工事について次を行います。

工事範囲を \([U, D] \times [L, R]\) とします。

調べるべき候補は以下の 4 種類です。

1. 上側：行 \(U-1\)、列 \(L\) から \(R\)
2. 下側：行 \(D+1\)、列 \(L\) から \(R\)
3. 左側：列 \(L-1\)、行 \(U\) から \(D\)
4. 右側：列 \(R+1\)、行 \(U\) から \(D\)

それぞれのマスについて、

• そのマスが建物 B
• まだ道路に面していると数えていない

ならば、新たに道路に面した建物として数えます。

一度道路に面した建物は、以降も道路に面したままです。
道路は増えるだけで減らないためです。

そのため、faced 配列で「すでに数えた建物かどうか」を管理すれば、同じ建物を二重に数えることを防げます。

また、工事によって E が R に変わりますが、実装ではグリッド S を更新していません。
これは、今後必要なのは「そのマスが建物かどうか」だけだからです。
道路に面した建物は faced で管理しているため、道路マス自体を明示的に更新しなくても正しく処理できます。

計算量

• 時間計算量: \(O\left(HW + \sum_{k=1}^{Q} \left(2(D_k-U_k+1) + 2(R_k-L_k+1)\right)\right)\)
• 空間計算量: \(O(HW)\)

初期状態の確認に \(O(HW)\) かかります。
各工事では長方形の周囲だけを調べるため、制約より全体で十分高速です。

実装のポイント

• 入力は 1-indexed ですが、実装では 0-indexed に直しています。

• グリッドの外に出ないように、上側は \(U > 0\) のときだけ、下側は \(D+1 < H\) のときだけ調べます。

• 同じ建物を複数回数えないように、faced 配列で管理します。

• 答え ans は建物数以下ですが、余裕を持って long long にしています。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, Q;
    cin >> H >> W >> Q;

    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    vector<string> faced(H, string(W, 0));
    long long ans = 0;

    const int di[4] = {-1, 1, 0, 0};
    const int dj[4] = {0, 0, -1, 1};

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] != 'B') continue;
            for (int d = 0; d < 4; d++) {
                int ni = i + di[d], nj = j + dj[d];
                if (0 <= ni && ni < H && 0 <= nj && nj < W && S[ni][nj] == 'R') {
                    faced[i][j] = 1;
                    ans++;
                    break;
                }
            }
        }
    }

    auto add = [&](int i, int j) {
        if (S[i][j] == 'B' && !faced[i][j]) {
            faced[i][j] = 1;
            ans++;
        }
    };

    while (Q--) {
        int U, D, L, R;
        cin >> U >> D >> L >> R;
        --U; --D; --L; --R;

        if (U > 0) {
            int r = U - 1;
            for (int c = L; c <= R; c++) add(r, c);
        }
        if (D + 1 < H) {
            int r = D + 1;
            for (int c = L; c <= R; c++) add(r, c);
        }
        if (L > 0) {
            int c = L - 1;
            for (int r = U; r <= D; r++) add(r, c);
        }
        if (R + 1 < W) {
            int c = R + 1;
            for (int r = U; r <= D; r++) add(r, c);
        }

        cout << ans << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。