[HNOI2012] 永无乡

这题折腾了两天了快（再也不想写数据结构了呜呜呜呜呜
这题大概就是在建任意一座桥对每一个点建动态开点权值线段树，联通性可以考虑使用并查集维护，对每个联通块的父亲维护一棵线段树，其余非父亲节点的线段树都可以删掉（节约空间。每次将两个联通块合并（即两个联通块建一座桥）也就是将两颗权值线段树进行合并操作。然后查询即查询当前联通块的第k大，随便查一下就可以了。（要注意空间问题，我卡了一下空间才勉强通过emmm

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100010
#define N 100000
#define mid ((l+r)>>1)
using namespace std;
int fa[maxn],n,m,s[maxn];
struct segtree{
    segtree *so[2];
    int sum;
    segtree(){
        so[0]=so[1]=NULL;
        sum=0;
    }
    void add(int l,int r,int v){
        if(l==r){
            sum++;
            return;
        }
        bool b=v>mid;
        if(b) l=mid+1;else r=mid;
        if(so[b]==NULL) so[b]=new segtree();
        so[b]->add(l,r,v);
        if(so[0]!=NULL)
            sum+=so[0]->sum;
        if(so[1]!=NULL)
            sum+=so[1]->sum;
    }
    int kth(int k,int l,int r){
        if(sum<k)return -1;
        int n=-1;
        if(l==r) {return sum==0?-1:s[l];}
        if(so[0]!=NULL&&so[0]->sum>=k) n=so[0]->kth(k,l,mid);
        else if(so[1]!=NULL){
            if(so[0]!=NULL)
                 n=so[1]->kth(k-so[0]->sum,mid+1,r);
            else n=so[1]->kth(k,mid+1,r);
        }
        return n;
    }
}*root[maxn];
segtree* merge_segtree(int l,int r,segtree *a,segtree *b){
    if(a==NULL)return b;
    if(b==NULL)return a;
    segtree *c=new segtree;
    c->sum=a->sum+b->sum;
    if(l==r)return c;
    c->so[0]=merge_segtree(l,mid,a->so[0],b->so[0]);
    c->so[1]=merge_segtree(mid+1,r,a->so[1],b->so[1]);
    return c;
}
int findfa(int x){
    if(x!=fa[x]){
        delete root[x];
        fa[x]=findfa(fa[x]);
    }
    return fa[x];
}
void prerun(){
    int a;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        root[i]=new segtree;
        scanf("%d",&a);
        s[a]=i;
        root[i]->add(0,N,a);
    }
}
void unity(int x,int y){
    x=findfa(x);
    y=findfa(y);
    if(x!=y){
        fa[x]=y;
        root[y]=merge_segtree(0,N,root[x],root[y]);
        delete root[x];
        root[x]=NULL;
    }
}
int q,x,y;
char tmp[3];
int main(){
    scanf("%d%d",&n,&m);
    prerun();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        unity(x,y);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%s%d%d",tmp,&x,&y);
        if(tmp[0]=='Q')
             printf("%d\n",root[findfa(x)]->kth(y,0,N));
        else unity(x,y);
    }
    return 0;
}