无向连通图的连通块可以用 dsu 维护。
每个连通块内用平衡树维护。
连边时检查两点是否连通，已连通就不用管，未连通就暴力启发式合并。
当然线段树合并也是可以的。
取根可以记录每个结点的父亲，平衡树的树高是期望 \(\log n\) 的。
输出岛编号的话可以直接让每个结点对应相同编号的岛，询问直接输出结点编号。
代码： 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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
int n,m,q;
int fa[N + 10];
inline int get(int x)
{
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
struct node
{
int val,rnd,sz,rk;
int lson,rson;
} tree[N + 10];
inline void up(int p)
{
tree[p].sz = tree[ls(p)].sz + 1 + tree[rs(p)].sz;
}
void split(int p,int v,int &x,int &y)
{
if(!p)
{
x = y = 0;
return ;
}
if(tree[p].val <= v)
x = p,split(rs(p),v,rs(p),y);
else
y = p,split(ls(p),v,x,ls(p));
up(p);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
if(tree[x].rnd < tree[y].rnd)
{
rs(x) = merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
int kth(int p,int k)
{
if(tree[ls(p)].sz + 1 == k)
return p;
else if(tree[ls(p)].sz >= k)
return kth(ls(p),k);
else
return kth(rs(p),k - tree[ls(p)].sz - 1);
}
void insert(int p,int &rt)
{
int x,y;
split(rt,tree[p].val,x,y);
rt = merge(merge(x,p),y);
}
void dfs(int p,int &rt)
{
if(!p)
return ;
dfs(ls(p),rt);
dfs(rs(p),rt);
ls(p) = rs(p) = 0;
insert(p,rt);
}
int merge_trees(int x,int y)
{
if(tree[x].sz < tree[y].sz)
swap(x,y);
dfs(y,x);
return x;
}
int main()
{
srand(19260817);
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(tree[i].val),tree[i].sz = 1,tree[i].rnd = rand(),fa[i] = i;
int x,y;
while(m--)
{
read(x),read(y);
if(get(x) ^ get(y))
{
int rt = fa[get(x)] = fa[get(y)] = merge_trees(get(x),get(y));
fa[rt] = rt;
}
}
read(q);
char op;
while(q--)
{
op = 0;
while(op < 'A' || op > 'Z')
op = gc();
read(x),read(y);
if(op == 'B')
{
if(get(x) ^ get(y))
{
int rt = fa[get(x)] = fa[get(y)] = merge_trees(get(x),get(y));
fa[rt] = rt;
}
}
else
{
if(tree[get(x)].sz < y)
puts("-1");
else
printf("%d\n",kth(get(x),y));
}
}
}