题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2733
我们对每一个连通块建一棵以排名为键值的权值线段树，询问就可以用二分的方法。
然后对于块与块间加边，我们用并查集维护连通性，每次合并两个块的时候，因为线段树结构相同，可以直接合并就行了。
1 #include2 #include 3 #include 4 using namespace std; 5 int inline readint(){ 6 int Num;char ch; 7 while((ch=getchar())<'0'||ch>'9');Num=ch-'0'; 8 while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0'; 9 return Num;10 }11 void outint(int x){12 if(x>=10) outint(x/10);13 putchar(x%10+'0');14 }15 int N,M,Q;16 int a[100010],re[100010];17 int Rt[100010],lc[2000010],rc[2000010],cnt=0;18 int sum[2000010];19 int fa[100010];20 int inline Getfa(int x){21 return fa[x]==x?x:fa[x]=Getfa(fa[x]);22 }23 void Pushup(int &rt){24 sum[rt]=sum[lc[rt]]+sum[rc[rt]];25 }26 void Insert(int &rt,int l,int r,int x){27 if(!rt) rt=++cnt;28 if(l==r){29 sum[rt]=1;30 return;31 }32 int mid=l+r>>1;33 if(x<=mid) Insert(lc[rt],l,mid,x);34 else Insert(rc[rt],mid+1,r,x);35 Pushup(rt);36 }37 int Merge(int x,int y){38 if(!x||!y) return x+y;39 lc[x]=Merge(lc[x],lc[y]);40 rc[x]=Merge(rc[x],rc[y]);41 Pushup(x);42 return x;43 }44 int Qry(int rt,int l,int r,int x){45 if(l==r) return l;46 int mid=l+r>>1;47 if(sum[lc[rt]]>=x) return Qry(lc[rt],l,mid,x);48 else return Qry(rc[rt],mid+1,r,x-sum[lc[rt]]);49 }50 int main(){51 N=readint();52 M=readint();53 for(int i=1;i<=N;i++){54 a[i]=readint();55 Insert(Rt[i],1,N,a[i]);56 re[a[i]]=i;57 }58 for(int i=1;i<=N;i++) fa[i]=i;59 for(int i=1;i<=M;i++){60 int A=readint(),61 B=readint(),62 fA=Getfa(A),63 fB=Getfa(B);64 fa[fB]=fA;65 Rt[fA]=Merge(Rt[fA],Rt[fB]);66 }67 Q=readint();68 for(int i=1;i<=Q;i++){69 char opt[5];70 scanf("%s",opt);71 int x=readint(),72 y=readint();73 switch(opt[0]){74 case 'Q':75 x=Getfa(x);76 if(sum[Rt[x]]