题目：
洛谷3224
分析：
这题一看\(n\leq100000\)的范围就知道可以暴力地用\(O(nlogn)\)数据结构乱搞啊……
每个联通块建一棵Splay树，查询就是Splay查询第k大的模板，建桥的时候就把两个联通块的Splay进行“启发式合并”
本来以为启发式合并是什么高端的东西，tzh神犇给我说就是把小的推倒然后暴力插入到大的里面2333
初始我给每个岛都建了一棵Splay树，合并\(a\), \(b\)两岛 (\(size_a<size_b\)) 时将\(a\)树插入到\(b\)树中，然后删除\(a\)树。合并两联通块同理。注意由于除了并查集祖先的树，该联通块中其他的树都已经被删除，所以要用并查集辅助记录哪个岛(\(b\))“代表”这个联通块
建桥时一定要判断两个点是否已经在同一联通块内，合并空树会RE！！！
我SB啊因为这个调一下午
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
namespace zyt
{
const int N = 100010;
int n, m, rank[N];
struct Splay
{
struct node
{
int val, id, size;
node *fa, *s[2];
node(node *const f, const int v, const int i):fa(f), val(v), id(i)
{
s[0] = s[1] = NULL;
size = 1;
}
}*head;
void update(node *rot)
{
rot->size = 1;
if (rot->s[0])
rot->size += rot->s[0]->size;
if (rot->s[1])
rot->size += rot->s[1]->size;
}
bool dir(const node *rot)
{
return rot == rot->fa->s[1];
}
void rotate(node *rot)
{
node *f = rot->fa, *ff = f->fa;
bool d = dir(rot);
rot->fa = ff;
if (ff)
ff->s[dir(f)] = rot;
else
head = rot;
f->s[d] = rot->s[!d];
if (rot->s[!d])
rot->s[!d]->fa = f;
f->fa = rot;
rot->s[!d] = f;
update(f);
update(rot);
}
void splay(node *rot, const node *goal = NULL)
{
while (rot && rot->fa != goal)
{
node *f = rot->fa, *ff = f->fa;
if (ff)
if (dir(rot) ^ dir(f))
rotate(rot), rotate(rot);
else
rotate(f), rotate(rot);
else
rotate(rot);
}
}
void insert(const int id, const int val)
{
node *rot = head;
if (rot == NULL)
head = new node(NULL, val, id);
else
{
while (1)
{
if (val < rot->val)
if (rot->s[0])
rot = rot->s[0];
else
{
rot->s[0] = new node(rot, val, id);
splay(rot->s[0]);
break;
}
else
if (rot->s[1])
rot = rot->s[1];
else
{
rot->s[1] = new node(rot, val, id);
splay(rot->s[1]);
break;
}
}
}
}
int find_kth(const int k)
{
int tmp = k;
node *rot = head;
while(1)
{
if (!rot)
return -1;
if ((!rot->s[0] && tmp == 1) || (rot->s[0] && tmp == rot->s[0]->size + 1))
return rot->id;
if (rot->s[0] && tmp <= rot->s[0]->size)
rot = rot->s[0];
else
{
if (rot->s[0])
tmp -= rot->s[0]->size;
tmp--;
rot = rot->s[1];
}
}
}
friend void merge(Splay &a, Splay &b);
friend void del(node *rot, Splay &d);
}island[N];
inline void merge(Splay &a, Splay &b)
{
if (a.head->size > b.head->size)
swap(a, b);
del(a.head, b);
a.head = NULL;
}
void del(Splay::node *rot, Splay &d)
{
d.insert(rot->id, rot->val);
if (rot->s[0])
del(rot->s[0], d);
if (rot->s[1])
del(rot->s[1], d);
delete rot;
}
int p[N];
int find(const int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
void work()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &rank[i]);
p[i] = i;
island[i].insert(i, rank[i]);
}
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
int x = find(a), y = find(b);
if (x == y)
continue;
p[x] = y;
merge(island[x], island[y]);
}
int q;
scanf("%d", &q);
while (q--)
{
char c;
int a, b;
do{c = getchar();} while (c != 'B' && c != 'Q');
scanf("%d%d", &a, &b);
if (c == 'B')
{
int x = find(a), y = find(b);
if (x == y)
continue;
p[x] = y;
merge(island[x], island[y]);
}
else
printf("%d\n", island[find(a)].find_kth(b));
}
}
}
int main()
{
zyt::work();
return 0;
}