今天我刷题了吗
搜索文档…
动态树
Link-Cut Tree
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
8
struct node {
9
int l, r;
10
int ch[2], fa;
11
int val, sum;
12
bool rev;
13
} tree[maxn];
14
15
template<typename T = int>
16
inline const T read()
17
{
18
T x = 0, f = 1;
19
char ch = getchar();
20
while (ch < '0' or ch > '9') {
21
if (ch == '-') f = -1;
22
ch = getchar();
23
}
24
while (ch >= '0' and ch <= '9') {
25
x = (x << 3) + (x << 1) + ch - '0';
26
ch = getchar();
27
}
28
return x * f;
29
}
30
31
template<typename T>
32
inline void write(T x, bool ln)
33
{
34
if (x < 0) {
35
putchar('-');
36
x = -x;
37
}
38
if (x > 9) write(x / 10, false);
39
putchar(x % 10 + '0');
40
if (ln) putchar(10);
41
}
42
43
inline int& ls(int cur)
44
{
45
return tree[cur].ch[0];
46
}
47
48
inline int& rs(int cur)
49
{
50
return tree[cur].ch[1];
51
}
52
53
inline bool get_rel(int cur, int fa)
54
{
55
return tree[fa].ch[1] == cur;
56
}
57
58
inline void connect(int cur, int fa, bool rel)
59
{
60
tree[fa].ch[rel] = cur;
61
tree[cur].fa = fa;
62
}
63
64
inline bool is_root(int cur)
65
{
66
return ls(tree[cur].fa) not_eq cur and rs(tree[cur].fa) not_eq cur;
67
}
68
69
inline void push_up(int cur)
70
{
71
tree[cur].sum = tree[cur].val xor tree[ls(cur)].sum xor tree[rs(cur)].sum;
72
}
73
74
inline void reverse(int cur)
75
{
76
swap(ls(cur), rs(cur));
77
tree[cur].rev xor_eq 1;
78
}
79
80
inline void push_down(int cur)
81
{
82
if (tree[cur].rev) {
83
reverse(ls(cur));
84
reverse(rs(cur));
85
tree[cur].rev = false;
86
}
87
}
88
89
inline void rotate(int cur)
90
{
91
int fa = tree[cur].fa;
92
int gf = tree[fa].fa;
93
bool rel = get_rel(cur, fa);
94
connect(tree[cur].ch[rel xor 1], fa, rel);
95
tree[cur].fa = gf;
96
if (not is_root(fa)) {
97
tree[gf].ch[get_rel(fa, gf)] = cur;
98
}
99
connect(fa, cur, rel xor 1);
100
push_up(fa);
101
push_up(cur);
102
}
103
104
inline void push_all(int cur)
105
{
106
if (not is_root(cur)) {
107
push_all(tree[cur].fa);
108
}
109
push_down(cur);
110
}
111
112
inline void splaying(int cur)
113
{
114
push_all(cur);
115
while (not is_root(cur)) {
116
int fa = tree[cur].fa;
117
int gf = tree[fa].fa;
118
if (not is_root(fa)) {
119
get_rel(cur, fa) xor get_rel(fa, gf) ? rotate(cur) : rotate(fa);
120
}
121
rotate(cur);
122
}
123
}
124
125
inline void access(int cur)
126
{
127
for (int pre = 0; cur; cur = tree[cur].fa) {
128
splaying(cur);
129
rs(cur) = pre;
130
push_up(cur);
131
pre = cur;
132
}
133
}
134
135
inline void make_root(int cur)
136
{
137
access(cur);
138
splaying(cur);
139
reverse(cur);
140
}
141
142
inline int find_root(int cur)
143
{
144
access(cur);
145
splaying(cur);
146
while (ls(cur)) {
147
push_down(cur);
148
cur = ls(cur);
149
}
150
splaying(cur);
151
return cur;
152
}
153
154
inline void link(int u, int v)
155
{
156
make_root(u);
157
if (find_root(v) not_eq u) {
158
tree[u].fa = v;
159
}
160
}
161
162
inline void cut(int u, int v)
163
{
164
make_root(u);
165
if (find_root(v) == u and tree[v].fa == u and not ls(v)) {
166
rs(u) = tree[v].fa = 0;
167
push_up(u);
168
}
169
}
170
171
inline void split(int u, int v)
172
{
173
make_root(u);
174
access(v);
175
splaying(v);
176
}
177
178
int main()
179
{
180
#ifndef ONLINE_JUDGE
181
freopen("input.txt", "r", stdin);
182
#endif
183
int n = read(), m = read();
184
for (int i = 1; i <= n; ++i) {
185
tree[i].val = read();
186
}
187
while (m--) {
188
int op = read(), x = read(), y = read();
189
if (op == 0) {
190
split(x, y);
191
write(tree[y].sum, true);
192
} else if (op == 1) {
193
link(x, y);
194
} else if (op == 2) {
195
cut(x, y);
196
} else {
197
splaying(x);
198
tree[x].val = y;
199
push_up(x);
200
}
201
}
202
return 0;
203
}
Copied!
最近更新 1yr ago
复制链接