题解 P3224 【[HNOI2012]永无乡】

· · 题解

本蒟蒻喜欢写指针+不记录父节点的splay，好像喜欢这样写的人不多哇。

关于本题思路： 就是用splay维护一下一个联通块中的名次，因为 题目保证重要度互不相同，所以先在读入的时候记录一下每个重要度对应的编号，splay里面直接插入这个重要度就行了。合并的话显然是并查集+启发式合并吧，把小得树的所有值一个一个直接插入到大的，然后把小的树删掉就行了

总的来说还是很easy的鸭，细节见代码吧，（最近有点小小的压行病，捂脸）

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,fa[MAXN],a[MAXN],x,u,v,q;
char c[10];
inline int findset(int x){return fa[x]==x?x:fa[x]=findset(fa[x]);}
struct node{
    node* ch[2];int v,s;
    node(int x){v=x;s=1;ch[0]=ch[1]=NULL;}
    inline int sz(int d){if (ch[d]) return ch[d]->s;return 0;}
    inline int cmp(int k){if (k==v) return -1;return k>v;}
    inline int cmp2(int k){if (k==sz(0)+1) return -1;if (k<=sz(0)) return 0;return 1;}
    inline void update(){s=sz(0)+sz(1)+1;}
} *root[MAXN];
inline void rot(node* &o,int d){node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o->update();k->update();o=k;}
inline void splay(node* &o,int k){
    int d=o->cmp2(k); if(d==1) k-=o->sz(0)+1;
    if(d!=-1){
        node* &p=o->ch[d];int d2=p->cmp2(k);int k2= (d2==0?k:k-(p->sz(0))-1);
        if(d2!=-1){splay(p->ch[d2],k2); if(d==d2) rot(o,d^1);else rot(o->ch[d],d2^1);}
        rot(o,d^1);
    }
}
inline void insert(node* &o,int v){if (o==NULL){o=new node(v);return;}int d=o->cmp(v);insert(o->ch[d],v);o->update();}
inline void merge(node* &p,node* &o){if (p->ch[0]) merge(p->ch[0],o);if (p->ch[1]) merge(p->ch[1],o);insert(o,p->v); delete p;p=NULL;}
inline void mergeset(int u,int v){
    int x=findset(u),y=findset(v);
    if (x!=y){
        if (root[x]->s<root[y]->s){fa[x]=y;merge(root[x],root[y]);}
        else{fa[y]=x;merge(root[y],root[x]);}
    }
}
inline int kth(node* &o,int k){if (k>o->s) return -1;splay(o,k);return o->v;}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&x),a[x]=i,insert(root[i],x),fa[i]=i;
    for (int i=1;i<=m;i++){scanf("%d%d",&u,&v);mergeset(u,v);} 
    scanf("%d",&q);
    for (int i=1;i<=q;i++){
        scanf("%s %d%d",c,&u,&v);
        if (c[0]=='B') mergeset(u,v);
        else{int t=kth(root[findset(u)],v);if (t==-1) printf("-1\n");else printf("%d\n",a[t]);}
    }
    return 0;
}