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
| #pragma GCC optimize(3)
#include<bits/stdc++.h>
#define fa(x) tr[x].p
#define lc(x) tr[x].s[0]
#define rc(x) tr[x].s[1]
#define notroot(x) lc(fa(x))==x||rc(fa(x))==x
const int N = 1e5+10;
int n,m;
struct node{
int s[2],p,v;
int sum,tag;
}tr[N];
/*不会改变虚实边*/
inline void pushup(int x){
tr[x].sum=tr[lc(x)].sum^tr[rc(x)].sum^tr[x].v;
}
inline void pushdown(int x){
if(tr[x].tag){
std::swap(lc(x),rc(x));
tr[lc(x)].tag^=1;
tr[rc(x)].tag^=1;
tr[x].tag=0;
}
}
inline void rotate(int x){
int y=fa(x),z=fa(y);
int k=rc(y)==x;
if(notroot(y)) tr[z].s[rc(z)==y]=x;
fa(x)=z;
tr[y].s[k]=tr[x].s[k^1];
fa(tr[x].s[k^1])=y;
tr[x].s[k^1]=y;
fa(y)=x;
pushup(y),pushup(x);
}
inline void pushall(int x){//递归 先到树根 然后一层一层 pushdown
if(notroot(x))pushall(fa(x));
pushdown(x);
}
inline void splay(int x){
pushall(x);
while(notroot(x)){
int y=fa(x),z=fa(y);
if(notroot(y))
(rc(y)==x)^(rc(z)==y)?rotate(x):rotate(y);
rotate(x);
}
}
/*会改变虚实边*/
inline void access(int x){//x到根节点权变成实边//
for(int y=0;x;){
splay(x);
rc(x)=y;
pushup(x);
y=x,x=fa(x);
}
}
inline void makeroot(int x){//原树中 x为原点
access(x);//打通路径
splay(x);//翻上来
tr[x].tag^=1;//旋转
}
inline void split(int x,int y){//将x y路径分离出来
makeroot(x);//将x变成树根
access(y);//给x于y通路 此时为啥不是直接是tr[x].sum 因为 通路之后 x不一定是平衡树的根节点
splay(y);//这里splay（x）splay（y）都可以 splay哪个就输出哪个
}
inline int findroot(int x){//找树根
access(x);
splay(x);
while(lc(x))
pushdown(x),x=lc(x);
splay(x);
return x;
}
inline void link(int x,int y){//连接
makeroot(x);//先看看是不是在一颗树内 先把x变成树根
if(findroot(y)!=x)fa(x)=y;//找出y的根是不是x 不是就把树x加到y里
}
inline void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&fa(y)==x&&!lc(y)){ //首先判断x y是否在一个平衡树里 然后 x是y的节点 然后x是y的前一个（因为平衡树有边 并不代表原树有边）
rc(x)=fa(y)=0;
pushup(x);
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>n>>m;
for(int i=1;i<=n;i++) std::cin>>tr[i].v;
while (m -- ){
int t,x,y;
std::cin>>t>>x>>y;
if(t==0){
split(x,y);
std::cout<<tr[y].sum<<"\n";
}
else if(t==1) link(x,y);
else if(t==2) cut(x,y);
else {
splay(x);
tr[x].v=y;
pushup(x);
}
}
}
|