P3300 [SDOI2013] Urban Planning

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.

- 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.

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.

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