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
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "rb", stdin);freopen(#x".out", "w+", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
namespace quickIO
{
const int MAXS = (1<<23);
char buf[MAXS], *p;
int len;
inline int read()
{
int data=0, w=1;
char ch=*p++;
while(ch!='-'&&(ch<'0'||ch>'9')&&p-buf<len&&(*p)) ch=*p++;
if(ch=='-') w=-1, ch=*p++;
while(ch>='0'&&ch<='9'&&p-buf<len&&(*p)) data=(data<<3)+(data<<1)+(ch^48), ch=*p++;
return data*w;
}
inline void init()
{
len = fread(buf,1,MAXS,stdin);
buf[len] = '\0';
p=buf;
}
}
using namespace quickIO;
const int maxn(300010);
int n, m;
int val[maxn], xr[maxn], fa[maxn], son[2][maxn], st[maxn], top;
bool rev[maxn];
inline bool isroot(int x) { return son[0][fa[x]]!=x && son[1][fa[x]]!=x; }
inline bool get_son(int x) { return son[1][fa[x]]==x; }
inline void update(int x) { xr[x]=xr[son[0][x]]^xr[son[1][x]]^val[x]; }
inline void pushdown(int x)
{
if(rev[x])
{
rev[son[0][x]]^=1;
rev[son[1][x]]^=1;
rev[x]=0;
swap(son[0][x], son[1][x]);
}
}
inline void rotate(int x)
{
int f=fa[x], g=fa[f], l=get_son(x), r=l^1;
if(!isroot(f)) son[get_son(f)][g]=x;
fa[x]=g; fa[f]=x; fa[son[r][x]]=f;
son[l][f]=son[r][x]; son[r][x]=f;
update(f); update(x);
}
inline void splay(int x)
{
top=1; st[1]=x;
for(RG int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
for(RG int i=top;i;i--) pushdown(st[i]);
for(;!isroot(x);rotate(x)) if(!isroot(fa[x])) rotate(get_son(fa[x])^get_son(x)?x:fa[x]);
}
inline void access(int x) { for(RG int t=0;x;t=x, x=fa[x]) splay(x), son[1][x]=t, update(x); }
inline void makeroot(int x) { access(x); splay(x); rev[x]^=1; }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { makeroot(x); fa[x]=y; }
inline void cut(int x, int y) { split(x, y); if(son[0][y]==x) son[0][y]=0; fa[x]=0; }
inline void change(int x, int y) { access(x); splay(x); val[x]=y; update(x); }
inline int query(int x, int y) { split(x, y); return xr[y]; }
inline int find(int x) { access(x); splay(x); while(son[0][x]) x=son[0][x]; return x; }
int main()
{
init();
n=read(); m=read();
for(RG int i=1;i<=n;i++) val[i]=xr[i]=read();
while(m--)
{
int ops=read(), x=read(), y=read();
if(ops==0) printf("%d\n", query(x, y));
else if(ops==3) change(x, y);
else
{
int fx=find(x), fy=find(y);
if(fx==fy && ops==2) cut(x, y);
if(fx!=fy && ops==1) link(x, y);
}
}
return 0;
}
|