bzoj2733: [HNOI2012]永无乡

题目
线段树合并复杂度： $O (合并的两棵树共同节点个数)$ 。
也就是说，大小为 $n$ 和 $m$ 的两棵线段树合并的复杂度是 $O (m i n (n, m))$ ，因为线段树大小为 $O (n l o g n)$ ，所以线段树合并的复杂度为 $O (n l o g n)$

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=100002,M=1800000;
int fa[N],i,x,y,rx,ry,rt[N],sum[M],L[M],R[M],n,m,v[N],id[N],t,cnt;
char s[2];
#define gc getchar
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(int a){if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){if(a<0)a=-a,putchar('-');wri(a),puts("");}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void ins(int &t,int l,int r,int x){
	if (!t) t=++cnt;
	if (l==r){
		sum[t]=1;
		return;
	}
	if (x<=mid) ins(L[t],l,mid,x);
	else ins(R[t],mid+1,r,x);
	sum[t]=sum[L[t]]+sum[R[t]];
}
int query(int t,int l,int r,int k){
	if (l==r) return l;
	if (k<=sum[L[t]]) return query(L[t],l,mid,k);
	return query(R[t],mid+1,r,k-sum[L[t]]);
}
int merge(int x,int y){
	if (!x || !y) return x+y;
	L[x]=merge(L[x],L[y]);
	R[x]=merge(R[x],R[y]);
	sum[x]=sum[L[x]]+sum[R[x]];
	return x;
}
int main(){
	n=rd(),m=rd();
	for (i=1;i<=n;i++) v[i]=rd(),fa[i]=i;
	for (;m--;){
		x=rd(),y=rd();
		fa[find(x)]=find(y);
	}
	for (i=1;i<=n;i++) ins(rt[find(i)],1,n,v[i]),id[v[i]]=i;
	m=rd();
	for (;m--;){
		scanf("%s",s),x=rd(),y=rd();
		rx=find(x);
		if (s[0]=='Q'){
			if (sum[rt[rx]]<y) puts("-1");
			else t=query(rt[rx],1,n,y),wln(id[t]);
		}
		else{
			ry=find(y);
			if (rx!=ry) fa[rx]=ry,rt[ry]=merge(rt[rx],rt[ry]);
		}
	}
}