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
|
#include <iostream>
const int maxm = 1e7 + 10;
static int n, m, val[maxm];
inline char ()
{
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int _read()
{
register char ch = nc();
register int sum = 0;
while (ch < '0' || ch > '9') ch = nc();
while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();
return sum;
}
static char pbuf[100000], *pp = pbuf;
inline void push(const char c)
{
if (pp - pbuf==100000) fwrite(pbuf, 1, 100000, stdout), pp = pbuf;
*pp++ = c;
}
inline void write(int x)
{
static int sta[35];
register int top = 0;
do {sta[top++] = x % 10, x /= 10;} while(x);
while (top) push(sta[--top] + '0');
}
namespace LCT
{
static int top, son[maxm][2], fa[maxm], xr[maxm], stk[maxm], rev[maxm];
inline void pushup(const int &x) { xr[x] = xr[son[x][1]] ^ xr[son[x][0]] ^ val[x]; }
inline void pushdown(const int& x)
{
if (rev[x])
{
rev[son[x][1]] ^= 1, rev[son[x][0]] ^= 1, rev[x] = 0;
std::swap(son[x][1], son[x][0]);
}
}
inline bool isroot(const int& x) { return (son[fa[x]][1] != x && son[fa[x]][0] != x); }
inline void rotate(const int& x)
{
register int fa1 = fa[x], fa2 = fa[fa1], l;
if (son[fa1][0] == x) l = 0;
else l = 1;
register int r = l ^ 1;
if (!isroot(fa1))
(son[fa2][0] == fa1) ? (son[fa2][0] = x) : (son[fa2][1] = x);
fa[x] = fa2, fa[fa1] = x, fa[son[x][r]] = fa1,
son[fa1][l] = son[x][r], son[x][r] = fa1,
pushup(fa1), pushup(x);
}
inline void splay(const int& x)
{
top = 1, stk[top] = x;
for (register int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
for (register int i = top; i; i--) pushdown(stk[i]);
while (!isroot(x))
{
register int y = fa[x], z = fa[y];
if (!isroot(y))
{
if ((son[y][0] == x) ^ (son[z][0] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x) { for (register int t = 0; x; t = x, x = fa[x]) splay(x), son[x][1] = t, pushup(x); }
inline void makeroot(const int &x) { access(x), splay(x), rev[x] ^= 1; }
inline int findroot(int x) { access(x), splay(x); while (son[x][0])x = son[x][0]; return x; }
inline void split(const int &x, const int &y) { makeroot(x), access(y), splay(y); }
inline void cut(const int &x, const int &y) { split(x, y); if (son[y][0] == x) son[y][0] = 0, fa[x] = 0; }
inline void link(const int &x, const int &y) { makeroot(x), fa[x] = y; }
};
int main()
{
n = _read(), m = _read();
for (register int i = 1; i <= n; i++) val[i] = _read(), LCT::xr[i] = val[i];
for (register int i = 1, opt, x, y; i <= m; i++)
{
opt = _read(), x = _read(), y = _read();
if (!opt)
{
LCT::split(x, y),
write(LCT::xr[y]), push('n');
}
if (opt == 1)
LCT::link(x, y);
if (opt == 2)
LCT::cut(x, y);
if (opt == 3)
LCT::access(x), LCT::splay(x), val[x] = y, LCT::pushup(x);
}
fwrite(pbuf, 1, pp - pbuf, stdout);
return 0;
}
|
近期评论