Description

The mayor of City A plans to develop a coastal strip, modeled as an $N \times M$ grid. Each cell can be a building, a road, or grassland. The strip is to be leased to companies, but the requirements are unusual: the buildings leased to a company must form a single connected component through roads. Each connected component can be leased to only one company.

The $N \times M$ grid is represented by the characters O, ., +, |, -, where O denotes a building, . denotes grassland. The symbols |, -, + denote roads, connecting up–down, left–right, and both up–down and left–right respectively. Orthogonally adjacent O cells are considered part of the same building.

Due to imperfect planning, some connected components may contain only roads; such components cannot be leased. Since the final selected plot may be co-developed with other cities, at the time of querying we will select a sub-rectangle of size $N_i \times M$ with $(0 < N_i \le N)$. The mayor wants software that supports:

1. Modifying a single cell.
2. Querying how many connected components within a specified strip contain at least one building.

Input Format

• The first line contains two integers $N, M$ as described.
• The next $N$ lines each contain $M$ characters describing the initial state of the strip.
• The next line contains an integer $Q$, the number of operations.
• Each of the following $Q$ lines is in one of the following formats:
  • C i j k: Change the cell at row $i$, column $j$ to character k.
    • k is one of O, ., +, |, -.
  • Q l r: Query the number of connected components that contain at least one building within the sub-rectangle with corners $(l, 1)$ and $(r, M)$.

Rows and columns are 1-indexed.

Output Format

For each Q operation, output one line with a single integer: the current number of connected components that contain at least one building in the specified strip.

4  4
.O..
O+O|
.O.. 
..OO
4
Q 1 4
C 2 4 + 
C 3 4 | 
Q 1 4

2 
1

Hint

Constraints: For $100\%$ of the testdata, $N \le 100000$, $M \le 6$, $Q \le 10000$.

Translated by ChatGPT 5