BZOJ 2733 「HNOI2012」永无乡

无向连通图的连通块可以用 dsu 维护。
每个连通块内用平衡树维护。

连边时检查两点是否连通，已连通就不用管，未连通就暴力启发式合并。
当然线段树合并也是可以的。

取根可以记录每个结点的父亲，平衡树的树高是期望 logn 的。
输出岛编号的话可以直接让每个结点对应相同编号的岛，询问直接输出结点编号。

代码：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
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));
        }
    }
}