Description
Input
Output
Sample Input
Sample Output
HINT
线段树 + 并查集, 暴力记录和更新一些信息, 详情见代码注解
- #include < cmath > #include < cstdio > #include < cstring > #include < iostream > #include < algorithm > #define inf 0x7f7f7f7f using namespace std;
- typedef long long ll;
- typedef unsigned int ui;
- typedef unsigned long long ull;
- inline int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- for (; ch < 0 || ch > 9; ch = getchar()) if (ch == -) f = -1;
- for (; ch >= 0 && ch <= 9; ch = getchar()) x = (x << 1) + (x << 3) + ch - 0;
- return x * f;
- }
- inline void print(int x) {
- if (x >= 10) print(x / 10);
- putchar(x % 10 + 0);
- }
- const int N = 2e2;
- int map[N + 10][N + 10];
- int ID[N * 4 + 10],
- fa[N * 4 + 10];
- int n,
- m;
- int find(int x) {
- return fa[x] == x ? x: fa[x] = find(fa[x]);
- }
- struct Segment {#define ls(p << 1)#define rs(p << 1 | 1) struct AC { // 线段树记录列数, struct 内存储一个列区间的信息
- int lcnt[N + 10],
- rcnt[N + 10]; // 记录最左列和最右列每行的联通块个数, 相当于编号
- int W,
- B,
- T; // 记录白块 (W), 黑块(B) 个数, T 为 lcnt[n]+rcnt[n]
- int l,
- r;
- void clear() {
- l = r = W = B = T = 0;
- memset(lcnt, 0, sizeof(lcnt));
- memset(rcnt, 0, sizeof(rcnt));
- }
- void init(int x) { // 单点暴力
- B = W = 0;
- for (int i = 1; i <= n; i++) {
- if (i == 1 || map[i][x] != map[i - 1][x]) map[i][x] ? B++:W++;
- lcnt[i] = rcnt[i] = B + W;
- }
- T = B + W;
- }
- }
- tree[N * 4 + 10];
- friend AC operator + (const AC & x, const AC & y) {
- AC z;
- z.clear();
- z.l = x.l,
- z.r = y.r;
- z.B = x.B + y.B;
- z.W = x.W + y.W;
- for (int i = 1; i <= x.T + y.T; i++) fa[i] = i,
- ID[i] = 0; //T 的用处(优化)
- for (int i = 1, p1, p2; i <= n; i++) { // 把 y 的信息加上 x.T, 使它们为一个图
- if (map[i][x.r] != map[i][y.l]) continue;
- if ((p1 = find(x.rcnt[i])) != (p2 = find(y.lcnt[i] + x.T))) {
- fa[p2] = p1; // 记得连向小的标号
- map[i][x.r] ? z.B--:z.W--;
- }
- }
- int Rank = 0;
- for (int i = 1; i <= n; i++) { // 离散化
- int p1 = find(x.lcnt[i]),
- p2 = find(y.rcnt[i] + x.T);
- if (!ID[p1]) ID[p1] = ++Rank;
- if (!ID[p2]) ID[p2] = ++Rank;
- z.lcnt[i] = ID[p1];
- z.rcnt[i] = ID[p2];
- }
- z.T = Rank;
- return z;
- }
- void build(int p, int l, int r) {
- tree[p].l = l,
- tree[p].r = r;
- if (l == r) {
- tree[p].init(l);
- return;
- }
- int mid = (l + r) >> 1;
- build(ls, l, mid),
- build(rs, mid + 1, r);
- tree[p] = tree[ls] + tree[rs];
- }
- void change(int p, int l, int r, int x) {
- if (l == r) {
- tree[p].init(l);
- return;
- }
- int mid = (l + r) >> 1;
- if (x <= mid) change(ls, l, mid, x);
- if (x > mid) change(rs, mid + 1, r, x);
- tree[p] = tree[ls] + tree[rs];
- }
- void work() {
- int x = read(),
- y = read();
- map[x][y] ^= 1;
- change(1, 1, n, y);
- printf("%d %d\n", tree[1].B, tree[1].W);
- }
- }
- T;
- int main() {
- n = read();
- for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map[i][j] = read();
- T.build(1, 1, n);
- m = read();
- for (int i = 1; i <= m; i++) T.work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2487627.html