BZOJ3673 可持久化并查集 by zky <可持久化数组>

Posted on Symbols count in article: 778 Reading time ≈ 3 mins.

Problem

可持久化并查集 by zky

Description

nn个集合 mm个操作
操作：
1  a  b1\;a\;b 合并a,ba,b所在集合
2  k2\;k 回到第kk次操作之后的状态(查询算作操作)
3  a  b3\;a\;b 询问a,ba,b是否属于同一集合，是则输出11否则输出00

Input

第一行两个整数n,mn,m
以后mm行，每行三个或两个整数opt  a  bopt\;a\;b或opt  kopt\;k，意义如上所述

Ouput

对于每个33操作，输出1/01/0

Sample Input

1
2
3
4
5
6
7
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
2
3
1
0
1

Hint

1<n,m≤2×1041 < n,m \le 2\times 10^4

标签：主席树 可持久化数组

Solution

本题的做法其实和并查集没太大关联。
如果是撤销，那可以用不加路径压缩的并查集完成，但是如果回到某时间，则不太好写。
这时，我们发现并查集这个东西构造其实很简单，只需要一个fafa数组就行了。所以我们自然可以想到直接用一个二维数组存储每个时间的fafa数组，即用增加的一维表示时间。
但是，nn、mm是2×1042\times 10^4级别，所以肯定会MLE\mathrm{MLE}，这里我们就需要用到主席树，把fafa数组可持久化。这里需要注意我们不能用路径压缩优化，因为我们需要回到前面的状态，为了让它跑得更快，我们可以用按秩合并优化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#define MAX_N 20000
using namespace std;
int n, m, cnt, now, root[MAX_N*10+5];
struct node {int fa, dep, ls, rs;} tr[MAX_N*100+5];
void build(int v, int l, int r) {
    if (l == r) {tr[v].fa = l;	return;}
    int mid = l+r>>1;
    tr[v].ls = ++cnt, tr[v].rs = ++cnt;
    build(tr[v].ls, l, mid);
    build(tr[v].rs, mid+1, r);
}
void modifyfa(int v, int o, int s, int t, int pos, int x) {
    tr[v] = tr[o];
    if (s == t)	{tr[v].fa = x;	return;}
    int mid = s+t>>1;
    if (pos <= mid)	modifyfa(tr[v].ls = ++cnt, tr[o].ls, s, mid, pos, x);
    else	modifyfa(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, pos, x);
}
void modifydep(int v, int s, int t, int pos) {
    if (s == t)	{tr[v].dep++;	return;}
    int mid = s+t>>1;
    if (pos <= mid)	modifydep(tr[v].ls, s, mid, pos);
    else	modifydep(tr[v].rs, mid+1, t, pos);
}
int find(int v, int s, int t, int pos) {
    if (s == t)	return v;
    int mid = s+t>>1;
    if (pos <= mid)	return find(tr[v].ls, s, mid, pos);
    else	return find(tr[v].rs, mid+1, t, pos);
}
int getf(int r, int x) {
    int pos = find(r, 1, n, x);
    if (tr[pos].fa != x)	return getf(r, tr[pos].fa);
    return pos;
}
int main() {
    scanf("%d%d", &n, &m);
    cnt = 0, root[0] = ++cnt;
    build(root[0], 1, n);
    for (int now = 1; now <= m; now++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            root[now] = root[now-1];
            int a, b;
            scanf("%d%d", &a, &b);
            int posa = getf(root[now], a), posb = getf(root[now], b);
            if (tr[posa].fa == tr[posb].fa)	continue;
            if (tr[posa].dep > tr[posb].dep)	swap(posa, posb);
            root[now] = ++cnt;
            modifyfa(root[now], root[now-1], 1, n, tr[posa].fa, tr[posb].fa);
            if (tr[posa].dep == tr[posb].dep)	modifydep(root[now], 1, n, tr[posb].fa);
        }
        if (opt == 2) {
            int k;
            scanf("%d", &k);
            root[now] = root[k];
        }
        if (opt == 3) {
            root[now] = root[now-1];
            int a, b;
            scanf("%d%d", &a, &b);
            if (tr[getf(root[now], a)].fa == tr[getf(root[now], b)].fa)	printf("1\n");
            else	printf("0\n");
        }
    }
    return 0;
}