洛谷P4121 [WC2005]双面棋盘

题目描述

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

我们把每行从上到下编号为，，，……， $n$ ，各列从左到右编号为， $2$ ， $3$ ，……， $n$ ，则每个格子可以用棋盘坐标表示。在上图中，有 $8$ 个格子黑色朝上，另外 $17$ 个格子白色朝上。

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

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

输入输出格式

输入格式：

输入文件的第一行包含一个正整数，为格子的边长。以下行每行个整数，非即，表示初始状态。表示白色，表示黑色。下一行包含一个整数，表示操作的数目。以下行每行两个整数 , ( ≤ , ≤ $n$ )，表示把坐标为的格子翻转。

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

4 3
5 2

说明

【样例说明】

翻转之后，棋盘变为：

有个黑色区域和 $3$ 个白色区域

翻转之后，棋盘变为：

有个黑色区域和个白色区域

【约定】

○ ≤ ≤

$本题有两种主流做法：LCT和线段树套并查集。这里我介绍线段树套并查集的做法。$

首先考虑维护联通块信息，可以用并查集。带修改呢可以用线段树解决。横着建线段树，每一个节点维护当前区间内最左边一列的联通情况，最右边一列的联通情况以及左右列每一个联通块的编号和黑白联通块的个数。

合并信息的时候我们就把左边和右边的联通块分别编号，枚举mid列和mid +1列是否相同。如果相同就合并所在联通块，在处理完这些之后再对新的联通块重新标号就好了。

常数跪了，日常开O2

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
int n, m, x, y, mp[maxn][maxn];

struct DSU {
    int fa[maxn];
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    void combine(int a, int b) {fa[find(a)] = find(b);} 
    void init() {for(register int i = 1; i <= n; ++i) fa[i] = i;}
};

struct DSU2 {
    int fa[maxn << 1];
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    void combine(int a, int b) {fa[find(a)] = find(b);} 
    void init() {for(register int i = 1; i <= n; ++i) fa[i] = i;}
};

namespace SGT {
    struct MSG {
        DSU L, R;
        int ans[2], pl[maxn], pr[maxn], cnt;
    };
    struct node {
        int ch[2];
        MSG msg;
    } tree[maxn << 1];
    #define LC(x) (tree[tree[x].ch[0]])
    #define RC(x) (tree[tree[x].ch[1]])
    #define LM(x) (tree[tree[x].ch[0]].msg)
    #define RM(x) (tree[tree[x].ch[1]].msg)
    int tmp[maxn * 2], nds[maxn * 2], cnt, root, lf, rf;
    DSU2 md; MSG ans;
    MSG merge(int l, int r, MSG a, MSG b) {
        ans.ans[0] = a.ans[0] + b.ans[0];
        ans.ans[1] = a.ans[1] + b.ans[1];
        memset(tmp, 0, sizeof(tmp));
        int ac = a.cnt, nxt, mid = l + r >> 1; 
        memcpy(ans.L.fa, a.L.fa, sizeof(a.L.fa));
        memcpy(ans.R.fa, b.R.fa, sizeof(b.R.fa));
        for(register int i = 1; i <= n * 2; ++i) md.fa[i] = i;
        for(register int i = 1; i <= n; ++i) 
            if(mp[i][mid] == mp[i][mid + 1]) {
                lf = md.find(a.pr[a.R.find(i)]);
                rf = md.find(ac + b.pl[b.L.find(i)]);
                if(lf != rf) md.combine(lf, rf), --ans.ans[mp[i][mid]];
            }
        int id = 0;
        memset(nds, 0, sizeof(nds));
        for(register int i = 1; i <= n; ++i) {
            if(!tmp[nxt = md.find(a.pl[i])]) tmp[nxt] = ++id;
            if(!nds[nxt]) nds[nxt] = i;
            ans.L.combine(nds[nxt], i);
            ans.pl[i] = tmp[nxt];
        }
        memset(nds, 0, sizeof(nds));
        for(register int i = 1; i <= n; ++i) {
            if(!tmp[nxt = md.find(ac + b.pr[i])]) tmp[nxt] = ++id;
            if(!nds[nxt]) nds[nxt] = i;
            ans.R.combine(nds[nxt], i);
            ans.pr[i] = tmp[nxt];
        }
        ans.cnt = id;
        return ans;
    }
    void push_up(int l, int r, int rt) {
        tree[rt].msg = merge(l, r, LM(rt), RM(rt));
    }
    void reset(int p, int rt) {
        int id = 1; MSG * now = &tree[rt].msg;
        now -> L.init(), now -> R.init();
        now -> pl[1] = now -> pr[1] = 1;
        now -> ans[0] = now -> ans[1] = 0;
        ++now -> ans[mp[1][p]];
        for(register int i = 1; i < n; ++i) {
            ++now -> ans[mp[i + 1][p]];
            if(mp[i][p] == mp[i + 1][p]) {
                --now -> ans[mp[i][p]];
                now -> L.combine(i, i + 1);
                now -> R.combine(i, i + 1);
            } else ++id;
            now -> pl[i + 1] = now -> pr[i + 1] = id;
        }
        now -> cnt = id;
    }
    void build(int l, int r, int & rt) {
        rt = ++cnt;
        if(l == r) {reset(l, rt); return ;}
        int mid = l + r >> 1;
        build(l, mid, tree[rt].ch[0]);
        build(mid + 1, r, tree[rt].ch[1]);
        push_up(l, r, rt);
    }
    void query() {
        printf("%d %d\n", tree[root].msg.ans[1], tree[root].msg.ans[0]);
    }
    void edit(int x, int y, int tl, int tr, int rt) {
        if(tl == tr) {reset(y, rt); return;}
        int mid = tl + tr >> 1;
        if(y <= mid) edit(x, y, tl, mid, tree[rt].ch[0]);
        else edit(x, y, mid + 1, tr, tree[rt].ch[1]);
        push_up(tl, tr, rt);
    }
}

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)	
            scanf("%d", &mp[i][j]);
    SGT::build(1, n, SGT::root);
    scanf("%d", &m);
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y), mp[x][y] ^= 1;
        SGT::edit(x, y, 1, n, 1);
        SGT::query();
    }
    return 0;
}

Rockdu's Blog