题解 P3224 【[HNOI2012]永无乡】

· · 题解

可以线段树合并啊QwQ

为什么要Splay啊

多难写QwQ

可以对于每一个点动态开点线段树，维护重要度。然后用并查集维护联通性，每次连边或者Build就把两棵线段树合并就好了啊QwQ

至于Query操作，就看看左儿子的sum与k的关系就好了

跑得还挺快

下面是代码

#include<cstdio>
#define N (200010)
using namespace std;
inline int read(int &data){
    data=0;char ch=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data;
}
struct xds{
    int l,r,sum,ch[2];
}t[N<<5];
int n,m,ind,T[N],fa[N],ans[N];
int ask(int x){return (fa[x]==x)?x:fa[x]=ask(fa[x]);}
int insert(int p,int l,int r){
    int rt=++ind;
    t[rt].l=l,t[rt].r=r,t[rt].sum=1;
    if(l==r)return rt; int mid=(l+r)>>1;
    if(p>mid)t[rt].ch[1]=insert(p,mid+1,r);
    else t[rt].ch[0]=insert(p,l,mid);
    return rt;
}
int unite(int L,int R,int l,int r){
    if(!L&&!R)return 0;
    if(!L)return R; if(!R)return L;
    int rt=++ind,mid=(l+r)>>1;
    t[rt].l=l,t[rt].r=r,t[rt].sum=t[L].sum+t[R].sum;
    t[rt].ch[0]=unite(t[L].ch[0],t[R].ch[0],l,mid);
    t[rt].ch[1]=unite(t[L].ch[1],t[R].ch[1],mid+1,r);
    return rt;
}
int query(int x,int k){
    if(t[x].sum<k)return -1;
    if(t[x].l==t[x].r)return ans[t[x].l];
    if(t[t[x].ch[0]].sum>=k)return query(t[x].ch[0],k);
    else return query(t[x].ch[1],k-t[t[x].ch[0]].sum);
}
int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++){fa[i]=i; int x;read(x),T[i]=insert(x,1,n),ans[x]=i;}
    for(int i=1;i<=m;i++){
        int x,y; read(x),read(y);
        int p=ask(x),q=ask(y);
        if(p!=q)fa[p]=q,T[q]=unite(T[p],T[q],1,n);
    }
    int Q; read(Q);
    while(Q--){
        int x,y; char c;
        c=getchar(); while(c!='B'&&c!='Q')c=getchar();
        read(x),read(y); if(c=='Q')printf("%d\n",query(T[ask(x)],y));
        else{int p,q;p=ask(x),q=ask(y);if(p!=q)fa[p]=q,T[q]=unite(T[p],T[q],1,n);}
    }
}