记录编号	568813	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.898 s
提交时间	2022-02-04 23:19:35	内存使用	70.80 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 5e6 + 5;
int pre[maxn],n,m,rt[maxn],sz = 0,a[maxn];
int key[maxm],son[maxm][2],rnd[maxm],Size[maxm],id[maxm];
void pushup(int x) {               
	Size[x] = Size[son[x][0]] + Size[son[x][1]] + 1;
	return ;
}
void rotate(int& x,int d) {
	int k = son[x][d ^ 1];
	son[x][d ^ 1] = son[k][d];
	son[k][d] = x;
	pushup(x);
	pushup(k);
	x = k;
	return ;
}
void insert(int& p,int x,int ID) {
	if(!p) {
		p = ++ sz;
		son[p][0] = son[p][1] = 0;
		rnd[p] = rand();
		key[p] = x;
		id[p] = ID;
		Size[p] = 1;
		return ;
	}
	int d = x > key[p];
	insert(son[p][d] , x , ID);
	if(rnd[son[p][d]] > rnd[p])rotate(p , d ^ 1);
	pushup(p);
	return ;
}
int kth(int p,int x) {
	if(Size[son[p][0]] >= x)return kth(son[p][0] , x);        
	else if(Size[son[p][0]] + 1 < x)return kth(son[p][1] , x - Size[son[p][0]] - 1);
	return id[p];
}
int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void dfs(int& p,int& fa) {
	insert(fa , key[p] , id[p]);
	if(son[p][0])dfs(son[p][0] , fa);
	if(son[p][1])dfs(son[p][1] , fa);
	return ;
}
void Merge(int x,int y) {
	x = find(x);
	y = find(y);
	if(x == y)return ;
	if(Size[rt[x]] > Size[rt[y]])swap(x , y);
	pre[x] = y;
	dfs(rt[x] , rt[y]);
	return ;
}
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]);
		pre[i] = i;
		insert(rt[i] , a[i] , i);
	}
	for(int i = 1;i <= m;++ i) {
		int u,v;
		scanf("%d%d",&u,&v);
		Merge(u , v);
	}
	int Q;
	scanf("%d",&Q);
	while(Q --) {
		char op;
		int x,y;
		scanf(" %c %d %d",&op,&x,&y);
		if(op == 'Q') {
			x = find(x);
			if(Size[rt[x]] < y) {
				puts("-1");
				continue ;
			}
			else printf("%d\n",kth(rt[x] , y));
		}
		else {
			Merge(x , y);
		}
	}
	return 0;
}