题目描述

ぬすけ君は、$N\ ×\ M$ のグリッドを持っています。行には上から順に $1$ から $N$、列には左から順に $1$ から $M$ の番号がついています。 グリッドの各マスは白か青かに塗られており、$S_{i,j}$ が $1$ のとき $i$ 行 $j$ 列のマスは青マス、$0$ のとき白マスです。 青く塗られた任意の二つのマス $a,b$ について、$a$ からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して $b$ に至るような経路のうち、同じマスを $2$ 度以上通らないようなものは、高々 $1$ 通りです。

ぬすけ君の永遠のライバルである怪盗スヌークは、ぬすけ君に $Q$ 個の質問をしました。$i$ 個目の質問は、$4$ つの整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ からなり、 グリッドの $x_{i,1}$ 行目から $x_{i,2}$ 行目まで、$y_{i,1}$ 列目から $y_{i,2}$ 列目までの範囲の長方形領域を切り出したときに、 その範囲の青マスからなる連結成分がいくつあるかを答える質問です。

怪盗スヌークの質問すべてに答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$ $S_{1,1}$..$S_{1,M}$ : $S_{N,1}$..$S_{N,M}$ $x_{1,1}$ $y_{i,1}$ $x_{i,2}$ $y_{i,2}$ : $x_{Q,1}$ $y_{Q,1}$ $x_{Q,2}$ $y_{Q,2}$

输出格式

質問ごとに、その範囲の青マスからなる連結成分がいくつあるかを出力せよ。

题目大意

题意:
$Nuske$ 现在有一个$N*M(N,M<=2000)$ 的矩阵$S$ , 若$S_i,j=1$ , 那么该处为蓝色, 否则为白色, 保证所有蓝色格子构成的连通块都是树.
给出$Q(Q<=200000)$ 次询问, 每次询问一个子矩阵中蓝色连通块的个数
输入:
第一行$N,M,Q$
接下来$N$ 行对应矩阵$S$ , 每行一个长度为$M$ 且只包含$0,1$ 的字符串
接下来$Q$ 行, 每行四个整数$x_1,y_1,x_2,y_2$ 表示相应询问
输出:
共$Q$ 行, 每行一个整数对应相应询问

感谢@凌幽 提供的翻译

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

3
2
2
2

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4

3
2
1
1
3
2

提示

制約

• $1\ ≦\ N,M\ ≦\ 2000$
• $1\ ≦\ Q\ ≦\ 200000$
• $S_{i,j}$ は $0$ または $1$ である
• $S_{i,j}$ は問題文中の条件を満たす
• $1\ ≦\ x_{i,1}\ ≦\ x_{i,2}\ ≦\ N(1\ ≦\ i\ ≦\ Q)$
• $1\ ≦\ y_{i,1}\ ≦\ y_{i,2}\ ≦\ M(1\ ≦\ i\ ≦\ Q)$

Sample Explanation 1

 $1$ つ目の質問では、グリッド全体が指定されます。青マスからなる連結成分は $3$ つあるので、$3$ を出力します。 $2$ つめの質問では、赤枠の範囲が指定されます。青マスからなる連結成分は $2$ つあるので、$2$ を出力します。 もとのグリッドで同じ成分に属するマスが、異なる成分に属するかもしれないことに注意してください。