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
|
#include <algorithm>
#include <cstring>
using namespace std;
struct {
int son[2],tag,val,sum;
}SPT[300100];
int fa[300100],sta[300100],topc,n,m;
void pushup(int o){
SPT[o].sum=SPT[SPT[o].son[0]].sum^SPT[o].val^SPT[SPT[o].son[1]].sum;
}
void pushdown(int o){
if(o&&SPT[o].tag){
swap(SPT[o].son[0],SPT[o].son[1]);
SPT[SPT[o].son[0]].tag^=1;
SPT[SPT[o].son[1]].tag^=1;
SPT[o].tag=0;
}
}
bool isroot(int o){
return (SPT[fa[o]].son[0]!=o)&&(SPT[fa[o]].son[1]!=o);
}
bool isrl(int o){
return SPT[fa[o]].son[1]==o;
}
void rorate(int o){
if(isroot(o))
return;
int f=fa[o];
int g=fa[f];
int which=isrl(o);
pushdown(f);
pushdown(o);
fa[o]=g;
if(!isroot(f))
SPT[g].son[SPT[g].son[1]==f]=o;
SPT[f].son[which]=SPT[o].son[which^1];
fa[SPT[o].son[which^1]]=f;
SPT[o].son[which^1]=f;
fa[f]=o;
pushup(f);
pushup(o);
}
void splay(int o){
topc=0;
int y=o;
sta[++topc]=y;
while(!isroot(y)){
sta[++topc]=fa[y];
y=fa[y];
}
for(int i=topc;i>=1;i--)
pushdown(sta[i]);
for(int f;!isroot(o);rorate(o)){
if(!isroot(f=fa[o]))
rorate((isrl(f)==isrl(o))?f:o);
}
}
void access(int o){
for(int y=0;o;o=fa[y=o]){
splay(o),SPT[o].son[1]=y,pushup(o);
}
}
void makeroot(int o){
access(o);
splay(o);
SPT[o].tag^=1;
pushdown(o);
}
int findroot(int o){
access(o);
splay(o);
pushdown(o);
while(SPT[o].son[0])
pushdown(o=SPT[o].son[0]);
return o;
}
void split(int x,int y){
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x)
fa[x]=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&fa[x]==y&&SPT[y].son[0]==x&&SPT[x].son[1]==0)
fa[x]=0,SPT[y].son[0]=0,pushup(y);
}
int query(int x,int y){
split(x,y);
return SPT[y].sum;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&SPT[i].val),SPT[i].sum=SPT[i].val;
for(int i=1;i<=m;i++){
int opt,x,y;
scanf("%d %d %d",&opt,&x,&y);
if(opt==0)
printf("%dn",query(x,y));
else if(opt==1)
link(x,y);
else if(opt==2)
cut(x,y);
else
splay(x),SPT[x].val=y;
}
return 0;
}
|
近期评论