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
| #define void inline void
const int maxn = 300000 + 5;
int n, m, a[maxn];
struct lct {
int fa[maxn], ch[maxn][2], rev[maxn], s[maxn];
int nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
int get(int x) { return ch[fa[x]][1] == x; }
void pushup(int x) {
s[x] = s[ch[x][0]] ^ s[ch[x][1]] ^ a[x];
}
void pushrev(int x) {
swap(ch[x][0], ch[x][1]);
rev[x] ^= 1;
}
void pushdown(int x) {
if (!rev[x]) return;
if (ch[x][0]) pushrev(ch[x][0]);
if (ch[x][1]) pushrev(ch[x][1]);
rev[x] = 0;
}
void rot(int x) {
int old = fa[x], oldf = fa[old], k = get(x), w = ch[x][k ^ 1];
if (nroot(old)) ch[oldf][ch[oldf][1] == old] = x;
ch[x][k ^ 1] = old; ch[old][k] = w;
if (w) fa[w] = old;
fa[old] = x; fa[x] = oldf;
pushup(old);
}
int st[maxn];
void splay(int x) {
int y = x, t = 0;
st[++t] = y;
while (nroot(y)) st[++t] = fa[y], y = fa[y];
while (t) pushdown(st[t--]);
while (nroot(x)) {
y = fa[x];
if (nroot(y)) rot(get(x) == get(y) ? y : x);
rot(x);
}
pushup(x);
}
void access(int x) {
for (int y = 0; x; y = x, x = fa[x])
splay(x), ch[x][1] = y, pushup(x);
}
void make(int x) {
access(x); splay(x); pushrev(x);
}
int findroot(int x) {
access(x); splay(x);
while (ch[x][0]) pushdown(x), x = ch[x][0];
return x;
}
void split(int x, int y) {
make(x); access(y); splay(y);
}
int link(int x, int y) {
make(x);
if (findroot(y) == x) return 0;
fa[x] = y;
return 1;
}
int cut(int x, int y) {
make(x);
if (findroot(y) != x || fa[x] != y || ch[x][1]) return 0;
fa[x] = ch[y][0] = 0;
pushup(y);
return 1;
}
int qpath(int l, int r) { split(l, r); return s[r]; }
void upoint(int x, int y) { splay(x); a[x] = y; }
} f;
|