以下の図で # で表される長方形領域が道路に変わるとき、新たに道路に隣接するようになる建物が存在しうるのは、 @ で表される位置に限ります。

........
..@@@@..
.@####@.
.@####@.
.@####@.
..@@@@..
........

\(\sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \leq 5 \times 10^6\) の制約より、各クエリに対してこのような位置を全て調べることで、実行時間制限に間に合わせることができます。

同じ建物を2度以上数えることがないようにするためには、道路に接続した建物は破壊するのが最も単純です。

実装例 (C++)

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

int main(){
  int h, w, q;
  cin >> h >> w >> q;
  vector<string> s(h);
  for(int i=0; i<h; i++) cin >> s[i];

  int ans = 0;
  vector<pair<int,int>> d4({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      if(s[i][j] == 'B'){
        bool ok = false;
        for(auto[di, dj]: d4){
          int ii = i + di;
          int jj = j + dj;
          if(0 <= ii && ii < h && 0 <= jj && jj < w && s[ii][jj] == 'R'){
            ok = true;
          }
        }
        if(ok){
          s[i][j] = '.';
          ans++;
        }
      }
    }
  }

  auto check=[&](int i, int j){
    if(s[i][j] == 'B'){
      s[i][j] = '.';
      ans++;
    }
  };

  for(int i=0; i<q; i++){
    int u, d, l, r;
    cin >> u >> d >> l >> r;
    u--, l--;
    if(l-1 >= 0){
      for(int i=u; i<d; i++){
        check(i, l-1);
      }
    }
    if(r < w){
      for(int i=u; i<d; i++){
        check(i, r);
      }
    }
    if(u-1 >= 0){
      for(int j=l; j<r; j++){
        check(u-1, j);
      }
    }
    if(d < h){
      for(int j=l; j<r; j++){
        check(d, j);
      }
    }

    cout << ans << endl;
  }
}

実装例 (Python)

H, W, Q = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == 'B':
      ok = False
      for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        ii = i + di
        jj = j + dj
        if 0 <= ii < H and 0 <= jj < W and S[ii][jj] == 'R':
          ok = True
      if ok:
        S[i][j]='.'
        ans += 1

def check(i, j):
  global ans
  if S[i][j] == 'B':
    S[i][j] = '.'
    ans += 1

for _ in range(Q):
  U, D, L, R = map(int, input().split())
  U -= 1
  L -= 1
  if L-1 >= 0:
    for i in range(U, D):
      check(i, L-1)
  if R < W:
    for i in range(U, D):
      check(i, R)
  if U-1 >= 0:
    for j in range(L, R):
      check(U-1, j)
  if D < H:
    for j in range(L, R):
      check(D, j)

  print(ans)