概要

各工事で空き地が道路に変わるたびに、道路に面している建物の数を求める問題です。
重要なのは、「新しく道路に面する可能性がある建物」は工事長方形のすぐ外側にある建物だけ、という点です。

考察

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

ある工事によって新しく道路に面する建物を考えます。

建物が新しく道路に面するためには、その建物の上下左右のどこかに「今回新しく道路になったマス」がある必要があります。

今回道路になるマスは、工事長方形の内部にあります。
したがって、それに隣接する建物は、工事長方形のすぐ外側にあるマスだけです。

具体的には、工事範囲が

• 行 \(U\) から \(D\)
• 列 \(L\) から \(R\)

であるとき、新しく道路に面する可能性がある建物は次の場所だけです。

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

つまり、長方形の外周に隣接する部分だけを調べれば十分です。

素朴な方法の問題点

各工事ごとに長方形内部のすべてのマスを道路に変え、さらに全建物を調べると、最悪で \(O(QHW)\) となり間に合いません。

また、長方形内部の全マスを毎回更新する方法も、長方形の面積が大きいと非常に重くなります。

しかし、この問題では以下の制約があります。

[ \sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \leq 5 \times 10^6 ]

これは、各工事の「外周の長さの合計」が十分小さいことを意味します。

そのため、各工事では長方形の外側の境界だけを調べれば高速に処理できます。

道路マスの更新は必要ない

一見すると、工事によって E を R に更新する必要がありそうです。
しかし、この解法では実際には道路マスの更新を行っていません。

理由は、建物が数えられるタイミングは「道路に面した瞬間」だけでよいからです。

ある工事で新しく道路が作られたとき、その道路に隣接する建物はその工事の直後に数えられます。
一度道路に面した建物は、その後もずっと道路に面したままなので、再び数える必要はありません。

そのため、各建物について「すでに道路に面しているか」を管理しておけば十分です。

アルゴリズム

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

各建物 B について、上下左右に初期道路 R があるかを調べます。
道路があれば、その建物はすでに道路に面しているので、答えに加えます。

この状態を exposed 配列で管理します。

• exposed[i][j] = 1：建物 \((i, j)\) はすでに道路に面している
• exposed[i][j] = 0：まだ道路に面していない

次に、各工事について以下を行います。

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

調べるべきマスは次の 4 辺です。

1. 上側：\((U-1, L), (U-1, L+1), \dots, (U-1, R)\)
2. 下側：\((D+1, L), (D+1, L+1), \dots, (D+1, R)\)
3. 左側：\((U, L-1), (U+1, L-1), \dots, (D, L-1)\)
4. 右側：\((U, R+1), (U+1, R+1), \dots, (D, R+1)\)

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

• そのマスが建物 B
• まだ exposed でない

なら、その建物は今回の工事で新しく道路に面したことになります。

そのため、

• exposed を 1 にする
• 答えを \(1\) 増やす

という処理を行います。

最後に、現在の答えを出力します。

計算量

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

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

実装のポイント

この実装では、盤面を 2 次元配列ではなく 1 次元の bytearray として扱っています。

幅を \(W+2\) にして、上下左右に番兵領域を追加しています。

WP = W + 2
size = (H + 2) * WP
grid = bytearray(size)

番兵を用意することで、例えば \(U=1\) のときに行 \(U-1=0\) を参照しても安全です。
番兵部分には B も R も入っていないため、特別な境界判定をせずに済みます。

また、bytearray を使うことで、文字列やリストのリストよりもメモリ使用量を抑えられます。

文字の判定には ASCII コードを使っています。

B = 66
ROAD = 82

これはそれぞれ、

• 'B' の ASCII コードが 66
• 'R' の ASCII コードが 82

であるためです。

各工事では、以下の 4 方向だけを確認します。

# 上側
row = (u - 1) * wp
for idx in range(row + l, row + r + 1):
    ...

# 下側
row = (d + 1) * wp
for idx in range(row + l, row + r + 1):
    ...

# 左側
idx = u * wp + (l - 1)
for _ in range(height):
    ...
    idx += wp

# 右側
idx = u * wp + (r + 1)
for _ in range(height):
    ...
    idx += wp

すでに数えた建物は exposed が 1 になっているため、同じ建物を重複して数えることはありません。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    H, W, Q = map(int, input().split())

    WP = W + 2
    size = (H + 2) * WP

    grid = bytearray(size)

    for i in range(1, H + 1):
        line = input().strip()
        start = i * WP + 1
        grid[start:start + W] = line

    exposed = bytearray(size)

    B = 66
    ROAD = 82

    ans = 0

    for i in range(1, H + 1):
        base = i * WP
        for idx in range(base + 1, base + W + 1):
            if grid[idx] == B:
                if (grid[idx - 1] == ROAD or grid[idx + 1] == ROAD or
                    grid[idx - WP] == ROAD or grid[idx + WP] == ROAD):
                    exposed[idx] = 1
                    ans += 1

    out = []
    append = out.append

    g = grid
    e = exposed
    wp = WP
    b = B

    for _ in range(Q):
        u, d, l, r = map(int, input().split())

        row = (u - 1) * wp
        for idx in range(row + l, row + r + 1):
            if g[idx] == b and e[idx] == 0:
                e[idx] = 1
                ans += 1

        row = (d + 1) * wp
        for idx in range(row + l, row + r + 1):
            if g[idx] == b and e[idx] == 0:
                e[idx] = 1
                ans += 1

        height = d - u + 1

        idx = u * wp + (l - 1)
        for _ in range(height):
            if g[idx] == b and e[idx] == 0:
                e[idx] = 1
                ans += 1
            idx += wp

        idx = u * wp + (r + 1)
        for _ in range(height):
            if g[idx] == b and e[idx] == 0:
                e[idx] = 1
                ans += 1
            idx += wp

        append(str(ans))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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