记录编号	586540	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.948 s
提交时间	2024-01-31 14:05:37	内存使用	31.09 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,q;
int a[N],idx,root[N],rnk[N];
struct B{
	int fa[N];
	void build(){
		for(int i = 1;i <= n;i++)fa[i] = i;
	}
	int find(int x){
		if(x == fa[x])return x;
		return fa[x] = find(fa[x]); 
	}
	void merge(int x,int y){
		x = find(x),y = find(y);
		if(x == y)return;
		fa[y] = x; 
	}//y -> x
}U;
struct Tree{
	int ls[N<<5],rs[N<<5],sum[N<<5];
	void add(int &p,int l,int r,int z){
		if(!p)p = ++idx;
		if(l == r)return sum[p] = 1,void();
		int mid = l + r >> 1;
		if(z <= mid)add(ls[p],l,mid,z);
		else add(rs[p],mid+1,r,z);
		sum[p] = sum[ls[p]] + sum[rs[p]]; 
	}
	int merge(int x,int y,int l,int r){
		if(!x)return y;
		if(!y)return x;
		if(l == r){
			sum[x] += sum[y];
			return x;
		}
		int mid = l + r >> 1;
		ls[x] = merge(ls[x],ls[y],l,mid);
		rs[x] = merge(rs[x],rs[y],mid+1,r);
		sum[x] = sum[ls[x]] + sum[rs[x]];
		return x;
	}
	int ask(int p,int l,int r,int k){
		if(l == r)return rnk[l];
		int mid = l + r >> 1,s = sum[ls[p]];
		if(s >= k)return ask(ls[p],l,mid,k);
		else return ask(rs[p],mid+1,r,k-s);
	}
}T;
int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
		rnk[a[i]] = i;
		T.add(root[i],1,n,a[i]);
	}
	U.build();
	for(int i = 1;i <= m;i++){
		int x,y;scanf("%d%d",&x,&y);
		x = U.find(x),y = U.find(y);
		if(x == y)continue;
		U.merge(x,y);
		T.merge(root[x],root[y],1,n);
	}
	scanf("%d",&q);
	for(int i = 1;i <= q;i++){
		char c[2];int x,y;
		scanf("%s%d%d",c,&x,&y);
		if(c[0] == 'Q'){
			if(T.sum[root[U.find(x)]] < y)printf("-1\n");
			else printf("%d\n",T.ask(root[U.find(x)],1,n,y));
		}
		else{
			x = U.find(x),y = U.find(y);
			if(x == y)continue;
			U.merge(x,y);
			T.merge(root[x],root[y],1,n);
		}
	}
	
	return 0;
	
}