BZOJ 2733 [HNOI2012]永无乡

题目大意

给你一堆点，要求你维护一个系统，支持：两个点之间连边；查询某点所在联通块内第k小值。

对于每一个点开一个动态开点权值线段树，xjb合并就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 100000
int n,m,q,fa[100010],root[100010],siz[2000010],inx,iny,tot,ls[2000010],rs[2000010],id[2000010];
char mode[3];
int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
void add(int &pos,int l,int r,int tx,int tg)
{
    if(!pos) pos=++tot;
    siz[pos]++;
    if(l==r) {id[pos]=tg;return;}
    int mid=(l+r)>>1;
    if(tx<=mid) add(ls[pos],l,mid,tx,tg);
    else add(rs[pos],mid+1,r,tx,tg);
}
int merge(int tx,int ty)
{
    if(!tx) return ty;
    if(!ty) return tx;
    siz[ty]+=siz[tx];
    ls[ty]=merge(ls[tx],ls[ty]),rs[ty]=merge(rs[tx],rs[ty]);
    return ty;
}
int lookfor(int pos,int l,int r,int tx)
{
    if(l==r) return id[pos];
    int mid=(l+r)>>1;
    if(tx<=siz[ls[pos]]) return lookfor(ls[pos],l,mid,tx);
    else return lookfor(rs[pos],mid+1,r,tx-siz[ls[pos]]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) fa[i]=i,scanf("%d",&inx),add(root[i],1,maxN,inx,i);
    while(m--)
    {
        scanf("%d%d",&inx,&iny);
        inx=unifind(inx),iny=unifind(iny);
        if(inx!=iny) fa[inx]=iny,root[inx]=merge(root[inx],root[iny]);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s%d%d",mode,&inx,&iny);
        switch(mode[0])
        {
            case 'B':
            {
                inx=unifind(inx),iny=unifind(iny);
                if(inx!=iny) fa[inx]=iny,root[iny]=merge(root[inx],root[iny]);
                break;
            }
            case 'Q':
            {
                inx=unifind(inx);
                if(iny==0||siz[root[inx]]<iny) printf("-1\n");
                else printf("%d\n",lookfor(root[inx],1,maxN,iny));
                break;
            }
        }
    }
}