BZOJ3674 可持久化并查集加强版

发表于

  题意:n个点，3种操作，强制在线:

  1、连边(a, b)

  2、跳到第k次操作之后的状态

  3、询问(a, b) 是否连通

  1和3操作是一个裸的并查集。
  2操作?暴力加边删边显然不可行。可持久化?
  我们发现并查集本质上就是一个数组。于是我们就是要将一个数组可持久化，支持查询每一个历史版本。
  我们可以用主席树来维护。主席树的叶子节点保存并查集数组，非叶子节点什么也不做。这样我们就保存下了每一个版本，只是数组中每一个元素的访问时间是$O(\log n)$的。
  需要注意的是不能只用路径压缩而不按秩合并。因为某一次路径压缩的复杂度是得不到保证的，我们不停退回执行某个卡路径压缩的操作就可以卡掉。事实上，使用了按秩合并之后，不用路径压缩复杂度也不会出现问题。
  代码中有一些细节，在注释中标出。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a);
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
const int maxn = 200010;
int n, m, lstans;
namespace PSGT
{
#define mid ((l + r) >> 1)
#define lc l, mid
#define rc mid + 1, r
    struct node
    {
        int ls, rs;
        int f, rnk;
        
        node(): ls(0), rs(0), f(0), rnk(0) { }
    } T[maxn * 2 * 18];
    int rt[maxn], cur;
    void creat(int& h, int l, int r)
    {
        h = ++cur;
        if(l == r) { T[h].f = l; return; }
        creat(T[h].ls, lc); creat(T[h].rs, rc);
    }
    void update(int& h, int l, int r, int pos, int x) // 新建版本;查找位置pos与修改值x均为真实节点编号
    {
        T[++cur] = T[h]; h = cur;
        if(l == r) { T[h].f = x; return; }
        if(pos <= mid) update(T[h].ls, lc, pos, x);
        else update(T[h].rs, rc, pos, x);
    }
    
    void addrnk(int h, int l, int r, int pos) // 无需新建版本
    {
        if(l == r) { ++T[h].rnk; return; }
        if(pos <= mid) addrnk(T[h].ls, lc, pos);
        else addrnk(T[h].rs, rc, pos);
    }
    int query(int h, int l, int r, int x)
    {
        if(l == r) return h;
        if(x <= mid) return query(T[h].ls, lc, x);
        else return query(T[h].rs, rc, x);
    }
}
using namespace PSGT;
int getf(int h, int v) // 返回真实节点在线段树上对应节点
{
    int p = query(h, 1, n, v);
    if(v == T[p].f) return p;
    return getf(h, T[p].f);
}
void merge(int a, int b, int h)
{
    a = getf(rt[h], a), b = getf(rt[h], b);
    if(T[a].f != T[b].f) // T[a].f == 真实a编号, T[b].f == 真实b编号
    {
        if(T[a].rnk > T[b].rnk) swap(a, b);
        update(rt[h], 1, n, T[a].f, T[b].f);
        if(T[a].rnk == T[b].rnk) addrnk(rt[h], 1, n, T[b].f);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); read(m);
    creat(rt[0], 1, n);
    rep(i, 1, m)
    {
        int op, a, b; read(op);
        if(op == 1)
        {
            rt[i] = rt[i - 1];
            read(a), read(b); a ^= lstans, b ^= lstans;
            merge(a, b, i);
        }
        if(op == 2) read(a), a ^= lstans, rt[i] = rt[a];
        if(op == 3)
        {
            rt[i] = rt[i - 1];
            read(a), read(b); a ^= lstans, b ^= lstans;
            lstans = (T[getf(rt[i], a)].f == T[getf(rt[i], b)].f ? 1 : 0);
            printf("%d\n", lstans);
        }
    }
    return 0;
}