Overview

This problem asks you to determine the number of buildings facing a road each time a construction converts vacant land into roads.
The key insight is that the only buildings that can newly face a road are those located just outside the construction rectangle.

Analysis

During construction, vacant land E within a rectangular region is converted to roads R.
It is also guaranteed that no buildings B are contained within the construction area.

Let’s consider which buildings newly face a road due to a given construction.

For a building to newly face a road, there must be a “cell that just became a road in this construction” adjacent to it (up, down, left, or right).

The cells that become roads are inside the construction rectangle.
Therefore, the buildings adjacent to them can only be cells just outside the construction rectangle.

Specifically, if the construction area covers:

• Rows \(U\) to \(D\)
• Columns \(L\) to \(R\)

then the only locations where buildings might newly face a road are:

• Top side: Row \(U-1\), columns \(L\) to \(R\)
• Bottom side: Row \(D+1\), columns \(L\) to \(R\)
• Left side: Column \(L-1\), rows \(U\) to \(D\)
• Right side: Column \(R+1\), rows \(U\) to \(D\)

In other words, it suffices to check only the part adjacent to the perimeter of the rectangle.

Problem with the Naive Approach

If we convert all cells inside the rectangle to roads and then check all buildings for each construction, the worst case is \(O(QHW)\), which is too slow.

Additionally, updating all cells inside the rectangle each time becomes extremely expensive when the rectangle’s area is large.

However, this problem has the following constraint:

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

This means the total perimeter length across all constructions is sufficiently small.

Therefore, each construction can be processed efficiently by examining only the outer boundary of the rectangle.

No Need to Update Road Cells

At first glance, it seems necessary to update E to R during construction.
However, this solution does not actually update road cells.

The reason is that we only need to count a building at the moment it becomes “facing a road.”

When a construction creates new roads, buildings adjacent to those roads are counted immediately after that construction.
Once a building faces a road, it continues to face a road forever, so there is no need to count it again.

Therefore, it suffices to maintain for each building whether it is “already facing a road.”

Algorithm

First, count the buildings that face a road in the initial state.

For each building B, check whether there is an initial road R in any of the four adjacent directions (up, down, left, right).
If there is a road, the building already faces a road, so add it to the answer.

This state is managed with an exposed array.

• exposed[i][j] = 1: Building \((i, j)\) already faces a road
• exposed[i][j] = 0: Does not yet face a road

Next, for each construction, do the following.

Let the construction area be \((U, D, L, R)\).

The cells to check are along the following 4 sides:

1. Top side: \((U-1, L), (U-1, L+1), \dots, (U-1, R)\)
2. Bottom side: \((D+1, L), (D+1, L+1), \dots, (D+1, R)\)
3. Left side: \((U, L-1), (U+1, L-1), \dots, (D, L-1)\)
4. Right side: \((U, R+1), (U+1, R+1), \dots, (D, R+1)\)

For each of these cells:

• If the cell is a building B
• And it is not yet exposed

then this building has newly become facing a road due to this construction.

Therefore, we:

• Set exposed to 1
• Increment the answer by \(1\)

Finally, output the current answer.

Complexity

• Time complexity: \(O(HW + \sum_{k=1}^{Q} ((D_k-U_k+1) + (R_k-L_k+1)))\)
• Space complexity: \(O(HW)\)

Checking the initial state takes \(O(HW)\).
Each construction only examines the perimeter of the rectangle, so the total is sufficiently fast given the constraints.

Implementation Details

In this implementation, the board is handled as a 1-dimensional bytearray instead of a 2-dimensional array.

The width is set to \(W+2\), adding sentinel regions on all four sides.

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

By using sentinels, for example when \(U=1\), referencing row \(U-1=0\) is safe.
Since the sentinel regions contain neither B nor R, no special boundary checks are needed.

Additionally, using bytearray reduces memory usage compared to strings or lists of lists.

Character comparisons use ASCII codes.

B = 66
ROAD = 82

These correspond to:

• The ASCII code of 'B' is 66
• The ASCII code of 'R' is 82

For each construction, only the following 4 directions are checked.

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

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

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

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

Since already-counted buildings have exposed set to 1, the same building is never counted more than once.

Source Code

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()

---

This editorial was generated by gpt-5.5-high.