LCT

题面

LCT板子

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
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 10;
int n,m,v[maxn],s[maxn],sum[maxn],fa[maxn],son[maxn][2],tag[maxn];
bool check(int x)
{
return (son[fa[x]][0] == x or son[fa[x]][1] == x);
}
void update(int x)
{
sum[x] = sum[son[x][0]] ^ sum[son[x][1]] ^ v[x];
}
void rev(int x)
{
swap(son[x][0],son[x][1]);
tag[x] ^= 1;
}
void push_down(int x)
{
if(tag[x]){
if(son[x][0])rev(son[x][0]);
if(son[x][1])rev(son[x][1]);
tag[x] = 0;
}
}
void rotate(int x)
{
int y = fa[x],z = fa[y],dir = son[y][1] == x;int opp = son[x][!dir];//与x处于相反位置的x的儿子
if(check(y))son[z][son[z][1] == y] = x;//把x顶替y的儿子位置
son[x][!dir] = y;//把x的反儿子置为y
son[y][dir] = opp;//把x原来的的位置变为它儿子
if(opp)fa[opp] = y;
fa[y] = x;
fa[x] = z;
update(y);
}
void splay(int x)
{
int y = x,top = 0,z;
s[++top] = y;
while(check(y))//因为要先把上面的标记放完。
{
y = fa[y];
s[++top] = y;
}
while(top)push_down(s[top--]);
while(check(x))
{
y = fa[x];z = fa[y];//y是父亲,z是祖父。
if(check(y))rotate((son[y][0] == x) ^ (son[z][0] == y) ? x : y);//如果y还不是根节点,就说明还可以旋
rotate(x);//无论怎么旋,最后都要旋x。
}
update(x);
}
void access(int x)//打通路径
{
for(int y = 0 ; x ; x = fa[y = x])
splay(x),son[x][1] = y,update(x);//先把x在其辅助树的位置变为根,再连虚边所指的父亲节点;
//此处须注意,因为我们最开始y为0,所以最开始把x旋到它在的辅助树的根时,我们设其右子树为0;
}
void make_root(int x)
{
access(x);splay(x);//先把x到根的路径打通,再把x在辅助树中splay为根
rev(x);//把整颗树翻转,即换根改深度。
}
void road(int x,int y)
{
make_root(x);//把x置为根
access(y);splay(y);//把y到x的路径打通
}
int find_root(int x)
{
access(x);splay(x);//把x旋到根后,最左边的节点就是根了
while(son[x][0])push_down(x),x = son[x][0];//一路往左。
splay(x);//再把原根旋回去
return x;
}
void link(int x,int y)
{
make_root(x);
if(find_root(y) != x)fa[x] = y;
}
void cut(int x,int y)
{
make_root(x);
if(find_root(y) == x and fa[y] == x and !son[y][0]){
fa[y] = son[x][1] = 0;
update(x);
}
}
signed main()
{
ios::sync_with_stdio(0);
// freopen("stdP3690.in","r",stdin);
// freopen("stdP3690.out","w",stdout);
cin >> n >> m;
for(int i = 1 ; i <= n ; ++ i)cin >> v[i];
while(m--)
{
int opt,x,y;
cin >> opt >> x >> y;
if(opt == 0){
road(x,y);
cout << sum[y] << endl;
}
if(opt == 1)link(x,y);
if(opt == 2)cut(x,y);
if(opt == 3)splay(x),v[x] = y;
}
return 0;
}