P3224 [HNOI2012] 永无乡

作为一个对平衡树几乎一窍不通的蒟蒻来说 这道题一看直接是懵逼的 还好有yyb大佬通俗易懂的题解 对于节点之间的连通性，考虑一个并查集来维护 这里采用启发式合并 启发式合并，即把size较小的平衡树合并到size较大的平衡树中 每一次合并时dfs遍历整个splay，把节点加入即可 查询时操作该节点所在集合的splay，找到第k小的值的编号即可 学到一招启发式合并~~（然而还是不会用）~~ ~~我严重怀疑我是不是不适合平衡树~~ ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register #define ls ch[now][0] #define rs ch[now][1] using namespace std; const int N=3e5+5; int n,m,tot,root[N],fa[N],f[N],h[N],val[N],size[N],ch[N][2]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline bool get(int x) { return ch[f[x]][1]==x; } inline void update(int now) { size[now]=size[ls]+size[rs]+1; } inline void rotate(int x)//通俗易懂的旋转 { int y=f[x],z=f[y],k=get(x),w=ch[x][k^1]; ch[y][k]=w; if (w) f[w]=y; ch[x][k^1]=y; f[y]=x; f[x]=z; if (z) ch[z][ch[z][1]==y]=x; update(y); update(x); } inline void splay(int x,int k) { while (f[x]!=k) { int y=f[x],z=f[y]; if (z!=k) rotate(get(y)==get(x)?y:x); rotate(x); } if (k<=n) root[k]=x; } inline void insert(int x,int bh)//把x加入bh所在集合的splay { int now=root[bh],u=bh; while (now&&val[now]!=x) u=now,now=ch[now][x>val[now]]; now=++tot; size[now]=1; f[now]=u; val[now]=x; ch[now][0]=ch[now][1]=0; if (u>n) ch[u][x>val[u]]=now; splay(now,bh); } void dfs(int now,int rt)//遍历整棵splay { if (ls) dfs(ls,rt); if (rs) dfs(rs,rt); insert(val[now],rt); } inline int findkth(int bh,int k)//在以bh为根的集合中找第k小 { int now=root[bh]; if (size[now]<k) return -1; while (1) { if (size[ls]>=k) now=ls; else if (size[ls]<k-1) { k-=size[ls]+1; now=rs; } else return val[now]; } } int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} inline void merge(int x,int y) { x=getfa(x),y=getfa(y); if (x==y) return; if (size[root[x]]>size[root[y]]) swap(x,y); fa[x]=y; dfs(root[x],y); } int main() { n=read(),m=read(); tot=(n<<1); for (reg int i=1;i<=n;i++) root[i]=i+n,fa[i]=i; for (reg int i=1;i<=n;i++) { int x=read(); h[x]=i;//x的位置 val[i+n]=x; size[i+n]=1; f[i+n]=i; } for (reg int i=1;i<=m;i++) merge(read(),read()); for (reg int q=read();q;q--) { char opt[5]; scanf("%s",opt); int x=read(),y=read(); if (opt[0]=='B') merge(x,y); else { int ans=findkth(getfa(x),y); printf("%d\n",ans==-1?ans:h[ans]); } } return 0; } ```