QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4135. 城市规划

统计

A市的市长打算在海边开发一段地带。这个地带看成是一个 $N \times M$ 的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司,但是这些公司的要求很奇怪, 他们要求租给他们的建筑要通过道路形成一个连通块,同一个连通块只能租给一家公司。这个 $N \times M$ 的方格阵是用字符组成的:O,.,+,|,-。其中 O 表示建筑。表示 . 草地。|,-,+表示道路,分别表示把上下,左右,上下左右的格子连起来。相邻的 O 表示这是一个建筑物。由于规划可能不太好,可能某些连通块里面只有道路,这里道路是不能出租的!由于最后这块地的选取可能有部分会与其他市共同开发,所以最后会在这个 $N \times M$ 中选取一段出来,最后选取出来的是一个 $N' \times M$($0 < N' \leq 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,输出一行,一个数字,表示当前的连通块个数。

样例数据

样例输入

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

样例输出

2
1

子任务

对于 $20\%$ 的数据,$N = 10^4, Q = 500$。

另有 $20\%$ 的数据,$M = 1$。

另有 $10\%$ 的数据,不存在 C 操作。

对于 $100\%$ 的数据,$1 \leq N \leq 100\,000$,$1 \leq M \leq 6$,$1 \leq Q \leq 10\, 000$。