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
118
119
120
| #include <bits/stdc++.h>
const int N = 1e5 + 100, inf = 0x3f3f3f3f;
int n, m, sum;
int fa[N];
struct LCT
{
struct Node
{
Node *fa, *ch[2];
int si, vs;
bool rev;
} tr[N];
const Node _null = {nullptr, nullptr, nullptr, 0, 0, false};
Node *null = (Node*)&_null, *tot = tr;
Node* _new()
{
*tot = {null, null, null, 1, 0, false};
return tot++;
}
void up(Node *x){ x->si = x->ch[0]->si + x->ch[1]->si + 1 + x->vs; }
void adt(Node *x){ std::swap(x->ch[0], x->ch[1]), x->rev ^= 1; }
void dw(Node *x)
{
if (x->rev)
{
adt(x->ch[0]), adt(x->ch[1]);
x->rev = false;
}
}
bool is_rt(Node *x){ return x->fa->ch[0] != x && x->fa->ch[1] != x; }
void rot(Node *x)
{
Node *y = x->fa, *z = y->fa;
bool k = y->ch[1] == x;
if (!is_rt(y)) z->ch[z->ch[1] == y] = x;
x->fa = z;
y->ch[k] = x->ch[k ^ 1], x->ch[k ^ 1]->fa = y;
x->ch[k ^ 1] = y, y->fa = x;
up(y);
}
void splay(Node *x)
{
static Node *stk[N];
Node *y = x, *z;
int top = 0;
stk[++top] = y;
while (!is_rt(y)) stk[++top] = y = y->fa;
while (top) dw(stk[top--]);
while (!is_rt(x))
{
y = x->fa, z = y->fa;
if (!is_rt(y)) (z->ch[1] == y) ^ (y->ch[1] == x) ? rot(x) : rot(y);
rot(x);
}
up(x);
}
void acs(Node *x)
{
for (Node *y = null; x != null; y = x, x = x->fa)
{
splay(x);
x->vs += x->ch[1]->si - y->si, x->ch[1] = y;
up(x);
}
}
void mk_rt(Node *x){ acs(x), splay(x), adt(x); }
void split(Node *x, Node *y){ mk_rt(x), acs(y); }
void link(int idx, int idy)
{
Node *x = tr + idx - 1, *y = tr + idy - 1;
mk_rt(x), acs(y), splay(y);
x->fa = y, y->vs += x->si;
up(y);
}
int work(int idx, int idy)
{
Node *x = tr + idx - 1, *y = tr + idy - 1;
split(y, x), splay(x);
bool odd = x->si & 1;
int res = inf, sum = x->si >> 1, ls = 0, rs = 0, ln, rn;
while (x != null)
{
dw(x);
ln = x->ch[0]->si + ls, rn = x->ch[1]->si + rs;
if (ln <= sum && rn <= sum)
{
res = std::min(res, int(x - tr + 1));
if (odd) break;
}
if (ln < rn) ls += x->ch[0]->si + x->vs + 1, x = x->ch[1];
else rs += x->ch[1]->si + x->vs + 1, x = x->ch[0];
}
splay(tr + res - 1);
return res;
}
} lct;
int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); }
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) lct._new(), fa[i] = i, sum ^= i;
while (m--)
{
int x, y, z;
char s[10];
scanf("%s", s + 1);
if (s[1] == 'X') printf("%d\n", sum);
else if (s[1] == 'Q') scanf("%d", &x), printf("%d\n", get(x));
else
{
scanf("%d %d", &x, &y);
lct.link(x, y);
x = get(x), y = get(y);
z = lct.work(x, y);
fa[x] = fa[y] = fa[z] = z;
sum ^= x ^ y ^ z;
}
}
return 0;
}
|