BZOJ1453: [Wc]Dface雙面棋盤

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 784 Solved: 422
[Submit][Status][Discuss]

Description

佳佳有一個 nnn 行 nnn 列的黑白棋盤，每個格子都有兩面，一面白色，一面黑色。佳佳把棋盤平放在桌子上，因此每個格子恰好一面朝上，如下圖所示：

QQ20180116200234.png

我們把每行從上到下編號為 111 ，222 ，333 ，……，nnn ，各列從左到右編號為 111 ，222 ，333 ，……，nnn ，則每個格子可以用棋盤坐標(x,y)(x, y)(x,y) 表示。在上圖中，有 888 個格子黑色朝上，另外 171717 個格子白色朝上。

如果兩個同色格子有一條公共邊，我們稱這兩個同色格子屬于同一個連通塊。上圖共有 555 個黑色連通塊和 333 個白色連通塊。

佳佳可以每分鐘將一個格子翻轉（即白色變成黑色，黑色變成白色），然后計算當前有多少個黑色連通塊和白色連通塊，你能算得更快嗎？

Input

輸入文件的第一行包含一個正整數 nnn ，為格子的邊長。以下 nnn 行每行 nnn 個整數，非 000 即 111 ，表示初始狀態。000 表示白色，111 表示黑色。下一行包含一個整數 mmm ，表示操作的數目。以下 mmm 行每行兩個整數 xxx , yyy (111 ≤ xxx , yyy ≤ nnn )，表示把坐標為(x,y)(x, y)(x,y) 的格子翻轉。

Output

輸出文件包含 mmm 行，每行對應一個操作。該行包括兩個整數 bbb , www ，表示黑色區域和白色區域數目。
【約定】

○1 ≤ n ≤ 200

○1 ≤ m ≤ 10,000

Sample Input

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

Sample Output

4 3
5 2

HINT

翻轉(3,2)(3, 2)(3,2) 之后，棋盤變為：

QQ20180116200629.png

有 444 個黑色區域和 333 個白色區域

翻轉(2,3)(2, 3)(2,3) 之后，棋盤變為：

QQ20180116200639.png

有 555 個黑色區域和 222 個白色區域

Source

鳴謝劉汝佳先生授權使用

題解

用線段樹維護行，并查集合并
線段樹每個節點維護區間[l,r]中，行l的并查集，行r的并查集，用于查詢l與r的聯通情況，維護[l,r]行的白色連通塊數和黑色連通塊數。維護并查集父節點個數。

合并即可。

注意，并查集維護的時候，其所指的父親不是這些格子自身，而是虛出來的節點。在兩個區間合并的時候，處理虛的節點的連通性，右區間虛節點編號要加上左區間虛的節點的個數，合并后的虛節點繼承回區間的左右并查集即可。離散化一下，不然可能會很大。。

推薦題解

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
inline int max(int a, int b){return a > b ? a : b;}
inline double max(double a, double b){return a - b > 0 ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline void read(int &x)
{x = 0;char ch = getchar(), c = ch;while(ch < '0' || ch > '9') c = ch, ch = getchar();while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 200 + 10;
int n, q, fa[MAXN << 2], g[MAXN][MAXN], vis[MAXN << 2];
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
struct Node
{int cnt, fal[MAXN << 1], far[MAXN << 1], wsize, bsize, l, r;Node(){cnt = wsize = bsize = l = r = 0, memset(fa, 0, sizeof(fa)), memset(far, 0, sizeof(far));}
}node[MAXN << 2];void pushup(int o)
{int l = o << 1, r = o << 1 | 1;if(node[l].cnt == 0){node[o] = node[r];return;}if(node[r].cnt == 0){node[o] = node[l];return;}for(int i = node[l].cnt + node[r].cnt;i;-- i) fa[i] = i, vis[i] = 0;node[o].wsize = node[l].wsize + node[r].wsize;node[o].bsize = node[l].bsize + node[r].bsize;for(int i = 1;i <= n;++ i)if(g[node[l].r][i] == g[node[r].l][i]){int f1 = find(node[l].far[i]), f2 = find(node[r].fal[i] + node[l].cnt);if(f1 != f2){fa[f1] = f2;if(g[node[l].r][i]) -- node[o].bsize;else -- node[o].wsize;}}node[o].cnt = 0;for(int i = 1;i <= n;++ i){int f1 = find(node[l].fal[i]), f2 = find(node[r].far[i] + node[l].cnt);if(!vis[f1]) vis[f1] = ++ node[o].cnt;if(!vis[f2]) vis[f2] = ++ node[o].cnt;node[o].fal[i] = vis[f1], node[o].far[i] = vis[f2];}
}
void calc(int o)
{int wsize = 0, bsize = 0, pos = node[o].l, *fal = node[o].fal, *far = node[o].far;if(g[pos][1]) ++ bsize; else ++ wsize;fal[1] = far[1] = 1;for(int i = 2;i <= n;++ i){if(g[pos][i] != g[pos][i - 1])if(g[pos][i]) ++ bsize;else ++ wsize;fal[i] = far[i] = wsize + bsize;}node[o].cnt = wsize + bsize, node[o].wsize = wsize, node[o].bsize = bsize;
}
void build(int o = 1, int l = 1, int r = n)
{node[o].l = l, node[o].r = r;if(l == r){calc(o);return;}int mid = (l + r) >> 1;build(o << 1, l, mid);build(o << 1 | 1, mid + 1, r);pushup(o);
}
void modify(int p, int o = 1, int l = 1, int r = n)
{if(l == r){calc(o);return;}int mid = (l + r) >> 1;if(p <= mid) modify(p, o << 1, l, mid);else modify(p, o << 1 | 1, mid + 1, r);pushup(o);
}int main()
{read(n);for(register int i = 1;i <= n;++ i)for(register int j = 1;j <= n;++ j)read(g[i][j]);build();read(q);for(register int i = 1;i <= q;++ i){int tmp1, tmp2;read(tmp1), read(tmp2);g[tmp1][tmp2] ^= 1;modify(tmp1);printf("%d %d\n", node[1].bsize, node[1].wsize);}return 0;
}