种类并查集学习笔记（CF1290C）

这题一眼种类并查集（，虽然我最开始没看出来并且也不熟悉种类并查集
好吧，其实是，我们不难发现，一个 \(S_i\) 最多只会对应两个 \(m_i\) 然后这两个 \(m_i\) 之间的关系是双向的，不能用 \(2-SAT\) 而且非常符合 种类并查集 的要求，那么考虑种类并查集，也就是把集合当作点 \(1\) ~ \(m\) 的点表示不选该集合， \(m + 1\) ~ \(2m\) 表示选该集合。
首先我们不难发现，如果记一个 \(i\) 第一个出现的集合的编号为 \(x_i\) ， 第二个为 \(y_i\) 那么当 \(S_i = 1\) 时，\(x_i\) ， \(y_i\) 要么都选，要么都不选。 \(S_i = 0\) 时则是一个选了另一个就不选。 那么我们只要统计 \(cnt_j\) 表示 \(j\) ( 可以是 \(x_i\) 也可以是 \(y_i\) ) 联通块中标号大于 \(m\) 的点的个数。
再考虑一下一个 \(S_i\) 只被一个集合覆盖的情况。
那么就是根据 \(S_i = 1\) \(or\) \(0\) 判定必须不选 \(or\) 选该集合，打一个 \(mus\) 标记即可。
代码

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
  x = 0; char ch = getchar(); bool flg = 0;
  for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  if (flg) x = -x;
  read(Ar...);  
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 3e5 + 10;
int n, m, ans, sz[N << 1], fa[N << 1], a[N], x[N], y[N], mus[N << 1], tot[N << 1], cur[N << 1];
char str[N];

inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]); 
}

inline void merge(int u, int v) {
    u = find(u), v = find(v);
    if (tot[u] < tot[v]) swap(u, v);
    if (u == v) {
        ans -= sz[u] * cur[u];
        cur[u] = 0;
        return ;
    }
    ans -= sz[u] * cur[u] + sz[v] * cur[v];
    cur[u] = cur[v] = 0;
    mus[u] |= mus[v];
    fa[v] = u;
    sz[u] += sz[v];
    tot[u] += tot[v];
}

int main(){
  //FO("");
    read(n, m);
    scanf("%s", str + 1);
    U(i, 1, n) a[i] = str[i] ^ 48;
    U(i, 1, m) {
        int cnt;
        read(cnt);
        while (cnt--) {
            int z;
            read(z);
            if (x[z]) y[z] = i;
            else x[z] = i;
        }
    }
    U(i, 1, m) cur[i] = 1, sz[i + m] = 1;
    U(i, 1, (m << 1)) fa[i] = i, tot[i] = 1;
    U(i, 1, n) {
        if (!x[i] && !y[i]) {
            writeln(ans);
            continue ;
        }
        if (!y[i]) {
            int u = find(x[i]), v = find(x[i] + m);
            if (a[i]) {
                if (!cur[u]) 
                    ans -= sz[v], ans += sz[u], cur[v] = 0, cur[u] = 1;
                mus[u] = 1;
            }
            else {
                swap(u, v);
                if (!cur[u]) 
                    ans -= sz[v], ans += sz[u], cur[v] = 0, cur[u] = 1;
                mus[u] = 1;
            }
            writeln(ans);
            continue ;
        }
        if (a[i]) {
            merge(x[i], y[i]), merge(x[i] + m, y[i] + m);
        }
        else {
            merge(x[i], y[i] + m), merge(x[i] + m, y[i]);
        }


        int u = find(x[i]), v = find(x[i] + m);
        if (mus[u] || (!mus[v] && sz[u] <= sz[v])) {
            ans += sz[u];
            cur[u] = 1;
        }
        else {
            ans += sz[v];
            cur[v] = 1;
        }
        writeln(ans);
    }
    return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16814506.html