对每个点建一棵线段树，连通时就合并，然后就没了。
线段树合并的细节有些多，检查了好久。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define pvi pair<vector<int>::iterator,int>
#define mkp make_pair
#define X first
#define Y second
#define LL long long
const int N=100005;
int n,m,rk[N],sa[N];
int rt[N],id;struct TREE{int lc,rc,sum;}T[7000000];
int par[N],sz[N];
void build(int x,int l,int r,int &num){
if(!num)num=++id;T[num].sum=1;
if(l==r)return;
int mid=l+r>>1;
if(x>mid)build(x,mid+1,r,T[num].rc);
else build(x,l,mid,T[num].lc);
}
int merge(int l,int r,int num1,int num2){
if(!num1)return num2;
if(!num2)return num1;
int mid=l+r>>1;
T[num1].lc=merge(l,mid,T[num1].lc,T[num2].lc);
T[num1].rc=merge(l,mid,T[num1].rc,T[num2].rc);
T[num1].sum=T[T[num1].lc].sum+T[T[num1].rc].sum;
return num1;
}
int getpar(int x){
if(par[x]!=x)par[x]=getpar(par[x]);
return par[x];
}
void cmb(int x,int y){
x=getpar(x),y=getpar(y);
if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
sz[par[y]=x]+=sz[y];
rt[x]=merge(1,n,rt[x],rt[y]);
}
int query(int k,int l,int r,int num){
if(l==r)return k==1?l:0;
int mid=l+r>>1;
if(!T[num].lc)return query(k,mid+1,r,T[num].rc);
if(!T[num].rc)return query(k,l,mid,T[num].lc);
int tmp=T[T[num].lc].sum;
return k>tmp?query(k-tmp,mid+1,r,T[num].rc):query(k,l,mid,T[num].lc);
}
int main(){
int i,x,y;char str[2];
scanf("%d%d",&n,&m);
sa[0]=-1;
rep(i,1,n){
scanf("%d",&rk[i]);
sz[sa[rk[i]]=par[i]=i]=1;
build(rk[i],1,n,rt[i]);
}
while(m--){
scanf("%d%d",&x,&y);
cmb(x,y);
}
for(scanf("%d",&m);m--;){
scanf("%s%d%d",str,&x,&y);
if(str[0]=='B')cmb(x,y);
else{
x=getpar(x);
printf("%d\n",sa[query(y,1,n,rt[x])]);
}
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-27394.html
