Comet OJ

C1850 [Contest #13]佛御石之钵-不碎的意志(困难版)

内存限制：256 MB 时间限制：2000 ms

题目描述

※ 简单版与困难版的唯一区别是 $n, m, q$ 的数据范围

给一个 $n \times m$ 的网格，每个格子里有一个数字，非 $0$ 即 $1$，行从上往下依次编号为 $1, 2, \cdots, n$，列从左往右依次编号为 $1, 2, \cdots, m$。

给 $q$ 次操作，每次给定一个以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的矩形内所有格子里的数字都变成 $1$。问每次操作之后，所有数字为 $1$ 的格子构成的四连通块的个数。

若不懂四连通块的定义可见最底下的提示。

输入格式

输入第一行两个整数 $n,m~(1 \le n,m \le 1\,000)$，表示网格大小。

接下来 $n$ 行，每行一个长为 $m$ 的 01 串，表示初始网格。

接下来一行一个整数 $q~(1 \le q \le 30\,000)$，表示操作个数。

接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2~(1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m)$ 表示把以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的矩形中的元素都变成 $1$。

输出

输出共 $q$ 行，每行一个整数，表示每次操作后含有数字 $1$ 的格子构成的四连通块的个数。

样例

样例输入 1

5 6
101010
000001
101010
000001
101010
3
1 2 5 2
4 4 4 4
1 3 3 6

样例输出 1

6
7
2

提示

关于四连通块的定义如下：

先定义两个相异格子 $A$ 和 $B$ 相邻当且仅当 $A$ 和 $B$ 拥有恰一个公共边，也就是格子 $B$ 紧邻在 $A$ 的上、下、左、右四个方向之一。

若相异两格子 $A$ 和格子 $B$ 属于同一个四连通块当且仅当下两两个条件都满足：

  1. $A$ 和 $B$ 里的数字一样

  2. $A$ 和 $B$ 相邻，或是存在 $k$ 个格子 $C_1, C_2, \ldots C_k$ ($k$ 可以是任意正整数。) 满足 $A$ 和 $C_1$ 相邻、$B$ 和 $C_k$ 相邻以及所有的 $C_i$ 和 $C_{i+1}$ 相邻($1 \le i < k$)