Overview

After each construction, we need to find the number of buildings that have a road adjacent to them (up, down, left, or right).
The key insight is that the only buildings that can newly become adjacent to a road due to a construction are those immediately outside the construction rectangle.

Analysis

During construction, empty lots E within the rectangular area become roads R.
It is also guaranteed that no buildings B are contained within the construction area.

Therefore, after construction, all cells within that rectangular area become roads.

Now, let’s consider buildings that newly become adjacent to a road due to a particular construction.

For a building to newly become adjacent to a road, there must be a cell that became a road in the current construction among its up/down/left/right neighbors.
Since the cells that become roads are inside the rectangle, the only buildings that can be newly affected are in these 4 locations:

• 1 row above the rectangle
• 1 row below the rectangle
• 1 column to the left of the rectangle
• 1 column to the right of the rectangle

In other words, we don’t need to examine the entire interior of the rectangle.

For example, suppose the construction area is the # portion below:

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

The only buildings that could newly become adjacent to a road are those in the outer cells directly adjacent (up/down/left/right) to #.
Since diagonal cells are not considered as facing a road, we don’t check diagonally outside the corners.

Naively re-examining the entire grid each time would result in \(O(QHW)\), which is too slow.
Also, filling in the entire interior of each construction area would be slow when the rectangle’s area is large.

On the other hand, this problem’s constraints guarantee that the total perimeter of construction areas

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

is small.
Therefore, we can process efficiently by only examining the parts adjacent to the perimeter of the rectangle for each construction.

Algorithm

First, count the buildings that are adjacent to a road in the initial state.

For each building B, check whether there is an R in any of the up/down/left/right directions.
If it faces a road, set faced[i][j] = true and increment the answer ans by 1.

Then, for each construction, do the following:

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

The candidates to check are the following 4 types:

1. Top side: row \(U-1\), columns \(L\) to \(R\)
2. Bottom side: row \(D+1\), columns \(L\) to \(R\)
3. Left side: column \(L-1\), rows \(U\) to \(D\)
4. Right side: column \(R+1\), rows \(U\) to \(D\)

For each of these cells:

• If the cell is a building B
• And has not yet been counted as facing a road

then count it as a building that newly faces a road.

Once a building faces a road, it remains facing a road from then on.
This is because roads only increase and never decrease.

Therefore, by managing “whether a building has already been counted” with the faced array, we can prevent counting the same building twice.

Also, although construction changes E to R, the implementation does not update the grid S.
This is because all we need going forward is “whether a cell is a building or not.”
Since buildings facing roads are managed by faced, we can process correctly without explicitly updating road cells.

Complexity

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

Checking the initial state takes \(O(HW)\).
For each construction, we only examine the perimeter of the rectangle, so it is sufficiently fast overall given the constraints.

Implementation Notes

• The input is 1-indexed, but the implementation converts to 0-indexed.

• To avoid going outside the grid, we only check the top side when \(U > 0\), and the bottom side only when \(D+1 < H\).

• The faced array is used to prevent counting the same building multiple times.

• The answer ans is at most the number of buildings, but long long is used for safety.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.