#P4121. [WC2005] 双面棋盘

    ID: 1024 远端评测题 700ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Link-Cut TreeLCT并查集生成树线段树WC/CTSC/集训队2005

[WC2005] 双面棋盘

题目描述

佳佳有一个 nnnn 列的黑白棋盘,每个格子都有两面,一面白色,一面黑色。佳佳把棋盘平放在桌子上,因此每个格子恰好一面朝上,如下图所示:

QQ20180116200234.png

我们把每行从上到下编号为 112233,……,nn,各列从左到右编号为 112233,……,nn,则每个格子可以用棋盘坐标(x,y)(x, y)表示。在上图中,有 88 个格子黑色朝上,另外 1717 个格子白色朝上。

如果两个同色格子有一条公共边,我们称这两个同色格子属于同一个连通块。上图共有 55 个黑色连通块和 33 个白色连通块。

佳佳可以每分钟将一个格子翻转(即白色变成黑色,黑色变成白色),然后计算当前有多少个黑色连通块和白色连通块,你能算得更快吗?

输入格式

输入文件的第一行包含一个正整数 nn,为格子的边长。以下 nn 行每行 nn 个整数,非 0011,表示初始状态。00 表示白色,11 表示黑色。

下一行包含一个整数 mm,表示操作的数目。以下 mm 行每行两个整数 xx, yy ( 1x,yn1 \le x,y \le n ),表示把坐标为 (x,y)(x, y) 的格子翻转。

输出格式

输出文件包含 mm 行,每行对应一个操作。该行包括两个整数 bb, ww,表示黑色区域和白色区域数目。

5
0 1 0 0 0
0 1 1 1 0
1 0 0 0 1
0 0 1 0 0
1 0 0 0 0
2
3 2
2 3
4 3
5 2

提示

【样例说明】

翻转 (3,2)(3, 2) 之后,棋盘变为:

QQ20180116200629.png

44 个黑色区域和 33 个白色区域

翻转 (2,3)(2, 3) 之后,棋盘变为:

QQ20180116200639.png

55 个黑色区域和 22 个白色区域

【数据范围】
对于 100%100\% 的数据,1n2001\le n \le 2001m1041\le m \le 10^4