幷查集

· · 个人记录

幷查集的作用

该数据结构主要用于判断两元素是否处在统一集合中，结构类似树，所以在特定题目中会带有边权，点权。

简单的幷查集。。。

太简单了，所以不讲了

各种题目

<<食物链>> in luogu

这道题目的元素关系共有三种，同类，猎物，天敌。故需要三种集合进行记录： x表示x的自己，x_{food}表示x的猎物，x_{ene}表示x的天敌。

首先解决合并集合

  1. 当出现表示x和y是同类的信息时，则把x所在的集合与y所在的集合合并，x_{food}所在的集合与y_{food}所在的集合合并，x_{ene}和y_{ene}同理。

  2. 当发现表示x吃y的信息时，则把x_{food}和y所在的集合合并，把x的所在的集合和y_{ene}所在的集合，又因为三种动物的食物链是环形的，所有又要把x_{ene}所在的集合和y_{food}所在的集合合并

再来解决判断

  1. 当出现表示x和y是同类的信息时，那么判断x所在的集合是否和y_{food}或者y_{ene}的集合一致或者y所在的集合是否和x_{food}或者x_{ene}的集合一致，如果符合，那么表示出现了矛盾，否则进行合并

  2. 类似1.，不说了

Code

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 50005;
int n, k, ans, c, a, b, fa[maxn << 2];

int getfa(int v) {
    return (fa[v] == v ? v : fa[v] = getfa(fa[v]));
}

void _union(int u, int v) {
    fa[getfa(u)] = getfa(v);
}

bool judge(int u, int v) {
    return getfa(u) == getfa(v);
}

int main() {
//  freopen("testdata.in", "r", stdin);
//  freopen("testdata.out", "w", stdout);

    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n * 3; i++) fa[i] = i;
    while(k--) {
        scanf("%d%d%d", &a, &b, &c);
        if (b > n || c > n) {
            ans++;
            continue;
        }
        if (a == 1) {
            if (judge(b + n, c) || judge(b + n + n, c))  {
                ans++;
                continue;
            }
            _union(b, c);
            _union(b + n, c + n);
            _union(b + n + n, c + n + n);
        } else {
            if (b == c || judge(b, c) || judge(b + n + n, c)) {
                ans++;
                continue;
            }
            _union(b, c + n + n);
            _union(b + n, c);
            _union(b + n + n, c + n);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Cude Stacking in poj

这道题目很明显地让我们求集合中信息（这道题求在方框x下共有多少个方块） 既然是集合，那么很自然的就想到幷查集，但是普通的幷查集并不能解决我们的问题，所以，我们要使用带权幷查集，要计算些什么呢？

  1. 在该方块下共有多少个方块down_x
  2. 这个比较难想到，就是所在的集合共有多少个方块size_x

现在要解决合并集合

首先，若把x所在的集合放到y的集合上，那么我们先找出x所在的集合的根节点rx和y所在集合的根节点ry, 然后把x集合并入y的集合，然后计算：

$size_{ry} = size_{rx} = size_{rx} + size_{ry}

在getfa（）中，找到v的父亲fv,首先计算出fv的节点值，然后使down_v = down_v + down_{fv}, size_v = size_{fv}

Code

思路已给，代码免发

Parity game in poj

这道题对思维的要求较高。 首先，部分和S_{l, r}，可用前缀和的差表示：sum_r - sum_{l-1} （PS：sum_i表示1~i中1的个数）

若[l, r]中1的个数为偶数，则表示sum_r与sum_{l-1}的奇偶性相同，反之则不同。 然后，我们发现

  1. 若s_i和s_j的奇偶性相同,且s_j与s_k的奇偶性相同，则s_i与s_k的奇偶性相同
  2. 若s_i和s_j的奇偶性相同,且s_j与s_k的奇偶性不同，则s_i与s_k的奇偶性不同
  3. 若s_i和s_j的奇偶性不同,且s_j与s_k的奇偶性相同，则s_i与s_k的奇偶性不同

至此，我们发现了这些值的奇偶关系具有传导性。还可以用位运算异或进行计算，用s_i ^ s_j表示两个值的奇偶性是否相同。

接着，想象一个简单的问题已知S_{1, 10}, S_{1, 3}, S_{7, 10}, 求S_{4,6}。

那当然就是S_{1, 10} \space xor \space S_{1, 3} \space xor \space S_{7, 10}

如果这个问题复杂了怎么办呢？这就引入今天的主角：幷查集。

我们可以使用区间的右端点和左端点-1作为节点，用区间的值作为边权。 而让节点的值d_x表示该节点+1到根结点的1的个数的奇偶性；

合并的时候，将左端点-1所在的集合并入右端点所在的集合。然后将左端点原先的根结点fx的d_{fx}改为d_x \space xor \space d_y \space xor \space S_{l,r}

路径压缩的部分，就是将其父亲计算出的值与自身进行异或即可得到新值。

顺道说一下，因为序列的长度特别大，所以需要进行离散化.

Code:

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 20005, maxq = 10005;
struct Query {
    int l, r, ans;
} qu[maxq];

//tmp***的变量是用来离散化的 
int n, m, tmp[maxn << 1], fa[maxn], d[maxn], tmp_tot;

void read() {
    scanf("%d%d", &n, &m);
    tmp_tot = 0;
    for (int i = 1; i <= m; i++) {
        char str[15];
        scanf("%d%d%s", &qu[i].l, &qu[i].r, str);
        qu[i].ans = (str[0] == 'o' ? 1 : 0);
        tmp[++tmp_tot] = qu[i].l - 1, tmp[++tmp_tot] = qu[i].r; 
    }
    sort(tmp + 1, tmp + 1 + tmp_tot);
    n = unique(tmp + 1, tmp + 1 + tmp_tot) - tmp - 1;
}

int find(int x) {
    int l = 1, r = n;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if (tmp[mid] == x) return mid;
        if (tmp[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

int getfa(int x) { 
    if (x == fa[x]) return x;
    int ro = getfa(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = ro;
}
int main() {
//  freopen("testdata.in", "r", stdin);
//  freopen("testdata.out", "w", stdout);
    read();
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int x = find(qu[i].l - 1), y = find(qu[i].r);
        int fx = getfa(x), fy = getfa(y);
        if (fx == fy) {
            if ((d[x] ^ d[y]) != qu[i].ans) 
                { printf("%d\n", i - 1); return 0; }
        } else fa[fx] = fy, d[fx] = d[x] ^ d[y] ^ qu[i].ans;
    }
    printf("%d\n", m);
    return 0;
}