luoguP3224 [HNOI2012]永无乡

· · 题解

原题传送门 >Here<

这道题基本就是一道平衡树水题。

建桥就相当于合并两棵平衡树，查询时查找树中第K小就可以了。

于是只剩下如何合并两棵平衡树的问题了。话说这道题真的很玄学，我本来以为有一种不明觉厉的方法可以迅速整体合并两棵平衡树，但是想了很久也没有想出来。看了各位dalao的博客才发现原来可以暴力把一棵平衡树的点全部拆出来插入到另一棵树上，并且每次合并两棵树时选取节点数少的树拆，据说这样可以保证每个点最多更新logn次（也就是启发式合并）。

然后就可以过了。。。

蒟蒻代码（用的是splay）：

#include <cstdio>

int lson[100001],rson[100001],father[100001],n,m,q,A,B,l,r,root[100001],size[100001],cnt,now,val[100001];
int belong[100001],faz,R,LS,L,RS,last;
char ch;
//lson,rson,father,val,size为splay树的信息，belong存储每个点在哪颗树里，root存储每棵树的根节点
inline void get(){
    ch=getchar();
    while(ch!='B'&&ch!='Q')ch=getchar();
}
inline bool son(int a,int b){return lson[a]==b;}
inline void LR(int x){
    if(!rson[x])return;
    faz=father[x],R=rson[x],LS=lson[R];
    if(!father[x])root[belong[x]]=R;
    father[R]=faz;
    size[R]=size[x];
    size[x]=size[lson[x]]+size[LS]+1;
    if(son(faz,x))lson[faz]=R;
    else if(faz)rson[faz]=R;
    father[x]=R,lson[R]=x,father[LS]=x,rson[x]=LS;
}
inline void RR(int x){
    if(!lson[x])return;
    faz=father[x],L=lson[x],RS=rson[L];
    if(!father[x])root[belong[x]]=L;
    father[L]=faz;
    size[L]=size[x];
    size[x]=size[rson[x]]+size[RS]+1;
    if(son(faz,x))lson[faz]=L;
    else rson[faz]=L;
    father[x]=L,rson[L]=x,father[RS]=x,lson[x]=RS;
}
void splay(int node,int ance){
    while(father[node]!=ance){
        if(father[father[node]]==ance){
            if(son(father[node],node))RR(father[node]);
            else LR(father[node]);
        }
        else{
            if(son(father[node],node)){
                if(son(father[father[node]],father[node]))RR(father[node]),RR(father[node]);
                else RR(father[node]),LR(father[node]);
            }
            else{
                if(son(father[father[node]],father[node]))LR(father[node]),RR(father[node]);
                else LR(father[node]),LR(father[node]);
            }
        }
    }
}
int findKth(int k,int node){
    if(size[node]<k||!node)return -1;
    while(size[lson[node]]!=k-1){
        if(size[lson[node]]>=k)node=lson[node];
        else k=k-size[lson[node]]-1,node=rson[node];
    } 
    return node;
}
void insert(int x,int t){
    cnt=root[t],last;
    while(cnt){
        size[cnt]++;
        last=cnt;
        if(val[cnt]>val[x])cnt=lson[cnt];
        else cnt=rson[cnt];
    }
    if(val[last]>val[x])lson[last]=x; else rson[last]=x;
    lson[x]=rson[x]=0;
    father[x]=last;
    belong[x]=t;
    size[x]=1;
    splay(x,0);
}
void MergeIn(int x,int t){
    if(!x)return;
    MergeIn(lson[x],t);
    MergeIn(rson[x],t);
    insert(x,t);
}
void merge(int a,int b){
    if(size[root[a]]>size[root[b]])a^=b^=a^=b;
    MergeIn(root[a],b);
}
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++)root[i]=i,belong[i]=i,size[i]=1;
    for(register int i=1;i<=n;i++)val[i]=read();
    for(register int i=1;i<=m;i++)A=read(),B=read(),merge(belong[A],belong[B]);
    q=read();
    for(register int i=1;i<=q;i++){
        get();
        A=read(),B=read();
        if(ch=='B')merge(belong[A],belong[B]);
        else printf("%d\n",findKth(B,root[belong[A]]));
    }
    return 0;
}