[SDOI2013] 城市规划
题目描述
A 市的市长打算在海边开发一段地带。这个地带看成是一个 $N \times M $ 的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司,但是这些公司的要求很奇怪。他们要求租给他们的建筑要通过道路形成一个连通块。同一个连通块只能租给一家公司。这个 $N\times M$ 的方格阵是用字符组成的:`O`,`.`,`+`,`|`,`-`,其中 `O` 表示建筑,'.' 表示草地。`|`,`-`,`+` 表示道路,分别表示把上下,左右、上下左右的格子连起来。相邻的 `O` 表示这是一个建筑物。
由于规划可能不太好,可能某些连通块里面只有道路,这里道路是不能出租的!由于最后这块地的选取可能有部分会与其他市共冋开发,所以最后会在这个 $N\times M$ 中选取一段出来,最后选取出来的是一个 $N_i\times M$($0<N_1\le N$)的地段。A 市的市长想弄要一个规划软件,支持以下功能:
1. 改变一个格子。
2. 询问某块地带有多少个带建筑的连通块。
输入输出格式
输入格式
第一行两个整数 $N, M$,如题意所示
接下来的 $N$ 行,每行 $M$ 个字符表示这片地带的初始情况。
接下来的一行一个整数 $Q$,表示操作次数。接下来的 $Q$ 行,每行有两种格式:
- `C i j k` : 把第 $i$ 行第 $j$ 个格子修改成k;
- `Q l r`: 询问 $(l, 1) (r, M)$ 这块地带连通块个数。
输出格式
对于每个询问中的 $Q$,输出一行,一个数字,表示当前的连通块个数。
输入输出样例
输入样例 #1
4 4
.O..
O+O|
.O..
..OO
4
Q 1 4
C 2 4 +
C 3 4 |
Q 1 4
输出样例 #1
2
1
说明
对于 $100\%$ 的数据,$N\le 100000, M\le 6, Q\le 10000$。