题意：
n个点，有加边操作，询问与某一点处于相同的联通块的点中权值第k大的点
思路：
对所有点建立一棵权值线段树，加边就配合并查集进行线段树合并
反思：
动态开点，权值线段树要用sum[g[x=find(x)]]（还是不够熟练），g为根。
代码：
1 #include<cstdio> 2 const int M=100005,N=5500000; 3 int sz,a[M],p[M],g[M],id[M],lc[N],rc[N],sum[N]; 4 char c[5]; 5 6 int read() 7 { 8 int x=0; char ch=getchar(); 9 while (ch<48 || ch>57) ch=getchar(); 10 while (ch>47 && ch<58) x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 11 return x; 12 } 13 14 int find(int x) { for (;x^p[x];x=p[x]=p[p[x]]); return x; } 15 16 void add(int l,int r,int &k,int x) 17 { 18 if (!k) k=++sz; ++sum[k]; 19 if (l==r) return; 20 int mid=l+r>>1; 21 if (x>mid) add(mid+1,r,rc[k],x); 22 else add(l,mid,lc[k],x); 23 } 24 25 int merge(int x,int y) 26 { 27 if (!x || !y) return x|y; 28 lc[x]=merge(lc[x],lc[y]),rc[x]=merge(rc[x],rc[y]); 29 sum[x]=sum[lc[x]]+sum[rc[x]]; 30 return x; 31 } 32 33 int ask(int l,int r,int cur,int k) 34 { 35 if (l==r) return l; 36 int mid=l+r>>1; 37 if (sum[lc[cur]]<k) return ask(mid+1,r,rc[cur],k-sum[lc[cur]]); 38 else return ask(l,mid,lc[cur],k); 39 } 40 41 int main() 42 { 43 int n=read(),m=read(),i,x,y; 44 for (i=1;i<=n;++i) id[a[i]=read()]=i,p[i]=i; 45 for (i=1;i<=m;++i) p[find(read())]=find(read()); 46 for (i=1;i<=n;++i) add(1,n,g[find(i)],a[i]); 47 for (m=read();m--;) 48 if (scanf("%s",c),x=read(),y=read(),c[0]=='Q') 49 if (sum[g[x=find(x)]]<y) puts("-1"); 50 else printf("%d\n",id[ask(1,n,g[x],y)]); 51 else 52 if ((x=find(x))^(y=find(y))) 53 if (sum[y]<sum[x]) p[y]=x,g[x]=merge(g[x],g[y]); 54 else p[x]=y,g[y]=merge(g[y],g[x]); 55 return 0; 56 }
转载于:https://www.cnblogs.com/HHshy/p/7189618.html
