写了线段树合并。。具体合并姿势和可并堆基本一样。。
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=100233,mxnode=maxn*20;
7 int lc[mxnode],rc[mxnode],sz[mxnode],tot;
8 int rt[maxn],fa[maxn],size[maxn];
9 int val[maxn],id[maxn];
10 int i,j,k,n,m,ans,P,K;
11
12 int ra;char rx;
13 inline int read(){
14 rx=getchar(),ra=0;
15 while(rx<'0'||rx>'9')rx=getchar();
16 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;
17 }
18
19 int merge(int x,int y,int a,int b){
20 if(!x||!y)return x|y;
21 sz[x]+=sz[y];if(a==b)return x;
22 int mid=a+b>>1;
23 lc[x]=merge(lc[x],lc[y],a,mid),rc[x]=merge(rc[x],rc[y],mid+1,b);
24 return x;
25 }
26 void query(int x,int a,int b){
27 if(a==b){ans=id[a];return;}
28 int mid=a+b>>1;
29 if(K<=sz[lc[x]])query(lc[x],a,mid);else K-=sz[lc[x]],query(rc[x],mid+1,b);
30 }
31 void build(int &x,int a,int b){
32 x=++tot,sz[x]=1;
33 if(a==b)return;
34 int mid=a+b>>1;
35 if(P<=mid)build(lc[x],a,mid);else build(rc[x],mid+1,b);
36 }
37
38 inline int getfa(int x){
39 return fa[x]!=x?fa[x]=getfa(fa[x]):x;
40 }
41 inline void con(int a,int b){
42 a=getfa(a),b=getfa(b);
43 if(a!=b)
44 fa[a]=b,rt[b]=merge(rt[b],rt[a],1,n),size[b]+=size[a];
45 }
46 int main(){
47 n=read(),m=read();
48 for(i=1;i<=n;i++)val[i]=read(),id[val[i]]=i,P=val[i],build(rt[i],1,n),fa[i]=i,size[i]=1;
49 for(i=1;i<=m;i++)con(read(),read());
50 m=read();char s[2];int x;
51 while(m--){
52 scanf("%s",s);
53 if(s[0]=='B')con(read(),read());else{
54 x=getfa(read()),K=read();
55 if(size[x]>=K)query(rt[x],1,n);else ans=-1;
56 printf("%d\n",ans);
57 }
58 }
59 return 0;
60 } View Code
转载于:https://www.cnblogs.com/czllgzmzl/p/5597024.html