题意：给出n个点，每个点给出权值，有2种操作 1.把两个点连接 2.询问某点处在联通块中第k小的点的编号
分析：把每个联通块建权值线段树，加上合并线段树操作。
技能：注意动态开点。
void insert(int &k,int l,int r,int val) { if (!k) k=++size; if (l==r) {sum[k]=1;return;} int mid=l+r>>1; if (val<=mid) insert(ls[k],l,mid,val); else insert(rs[k],mid+1,r,val); sum[k]=sum[ls[k]] + sum[rs[k]]; }
代码：
#include<bits/stdc++.h> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;++i) #define dep(i,j,k) for (int i=j;i>=k;--i) #define to e[i].v #define Cl(a) memset(a,0,sizeof(a)) #define N 100010 int fa[N],root[N],sum[N*80],ls[N*80],rs[N*80],v[N],id[N]; int q,size,n,m; int read() { int f=1,x=0;char ch=getchar(); for (;ch>'9'||ch<'0';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);} void insert(int &k,int l,int r,int val) { if (!k) k=++size; if (l==r) {sum[k]=1;return;} int mid=l+r>>1; if (val<=mid) insert(ls[k],l,mid,val); else insert(rs[k],mid+1,r,val); sum[k]=sum[ls[k]] + sum[rs[k]]; } int query(int k,int l,int r,int val) { if (l==r) return l; int mid=l+r>>1; if (val<=sum[ls[k]]) return query(ls[k],l,mid,val); else return query(rs[k],mid+1,r,val-sum[ls[k]]); } int merge(int x,int y) { if (!x) return y; if (!y) return x; ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); sum[x]=sum[ls[x]]+sum[rs[x]]; return x; } int main() { n=read(); m=read(); rep(i,1,n) v[i]=read(),fa[i]=i; rep(i,1,m) { int u=read(),v=read(),fu=find(u),fv=find(v); fa[fv]=fu; } rep(i,1,n) { insert(root[find(i)],1,n,v[i]); id[v[i]]=i; } q=read(); char ch[10]; int x,y; rep(i,1,q) { scanf("%s",ch); x=read(); y=read(); if (ch[0]=='Q') { int fx=find(x); if (sum[root[fx]]<y) {puts("-1");continue;} int t=query(root[fx],1,n,y); printf("%d\n",id[t]); } else { int fx=find(x),fy=find(y); if (fx^fy) { fa[fy]=fx; root[fx]=merge(root[fx],root[fy]); } } } return 0; }
