forked from ShahjalalShohag/code-library
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPersistent UnionFind.cpp
More file actions
127 lines (126 loc) · 3.43 KB
/
Copy pathPersistent UnionFind.cpp
File metadata and controls
127 lines (126 loc) · 3.43 KB
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
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
template<typename T>
struct PersistentArray { // 0-indexed
struct node {
node* l, * r; T x;
};
int n = 1;
vector<node*> root;
int build(vector<T> v) {
while (n < v.size()) n <<= 1;
root.push_back(build(0, n - 1, v));
return root.size() - 1;
}
node* build(int l, int r, vector<T>& v) {
node* cur = new node();
if (l == r) {
if (l < v.size()) cur -> x = v[l];
else cur -> x = 0;
}
else {
cur -> l = build(l, (l + r) >> 1, v);
cur -> r = build(((l + r) >> 1) + 1, r, v);
}
return cur;
}
// get the ith value of the rth array
T get_val(int r, int i) {
return get_val(root[r], i, 0, n - 1);
}
T get_val(node* cur, int i, int l, int r) {
if (l == r) return cur -> x;
if (i <= ((l + r) >> 1)) return get_val(cur -> l, i, l, (l + r) >> 1);
else return get_val(cur -> r, i, ((l + r) >> 1) + 1, r);
}
// update the ith value if the rth array by x and return the new root of the array
int upd(int r, int i, T x) {
root.push_back(upd(root[r], i, x, 0, n - 1));
return root.size() - 1;
}
void set(int r, int i, T x) {
int k = upd(r, i, x);
root[r] = root[k];
root.pop_back();
}
node* upd(node* pre, int i, T x, int l, int r) {
node* cur = new node();
if (l == r){
cur -> x = x;
}
else {
if (i <= ((l + r) >> 1)) {
cur -> l = upd(pre -> l, i, x, l, (l + r) >> 1);
cur -> r = pre -> r;
}
else {
cur -> l = pre -> l;
cur -> r = upd(pre -> r, i, x, ((l + r) >> 1) + 1, r);
}
}
return cur;
}
};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct PersistentDSU {
PersistentArray<int> par, sz;
vector<int> c; int cur = 0;
PersistentDSU() {}
PersistentDSU(int n, int q) { // q -> maximum instances of DSU
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
p[i] = i;
}
par.build(p);
sz.build(vector<int> (n + 1, 1));
c.resize(q + 1, n); cur = 0; // initial DSU is the 0th one
}
int find(int r, int u) {
int p = par.get_val(r, u);
if (p == u) return u;
int cur = find(r, p);
par.set(r, u, cur);
return cur;
}
bool same(int r, int u, int v) { return find(r, u) == find(r, v); }
int get_size(int r, int u) { return sz.get_val(r, find(r, u)); }
int count(int r) { return c[r]; } //connected components
int merge(int r, int u, int v) { // returns the updated root
cur++;
c[cur] = c[r];
if ((u = find(r, u)) == (v = find(r, v))) {
par.upd(r, 0, 0);
sz.upd(r, 0, 0);
// assert(cur == par.root.size() - 1);
return cur;
}
else c[cur]--;
if (rnd() % 2) swap(u, v);
int x = sz.get_val(r, v) + sz.get_val(r, u);
par.upd(r, u, v);
sz.upd(r, v, x);
// assert(cur == par.root.size() - 1);
return cur;
}
};
int r[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
PersistentDSU d(n, q + 1);
for (int i = 1; i <= q; i++) {
int ty, id, u, v; cin >> ty >> id >> u >> v;
++id, ++u; ++v;
if (ty == 0) {
r[i] = d.merge(r[id], u, v);
}
else {
r[i] = r[i - 1];
cout << d.same(r[id], u, v) << '\n';
}
}
return 0;
}
// https://judge.yosupo.jp/problem/persistent_unionfind