【并查集+线段树合并】永无乡

并查集, 线段树

传送门：CodeVS1477

HNOI的题

经典做法是平衡树+启发式+并查集合并？！反正我不会（至少现在）

于是写了线段树合并+并查集

思路比较清楚的，就是连一条边就合并一下

具体见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,p,tot,x,y,a[100030],head[100030],id[100030],fa[100030],sum[100030*30],ls[100030*30],rs[100030*30];
char ch;
void set_up(int &k,int x,int l,int r){
	k=++tot;
	if (l==r){
		sum[k]++;
		return;
	}
	
	int mid=(l+r)>>1;
	if (x<=mid) set_up(ls[k],x,l,mid); else set_up(rs[k],x,mid+1,r);
	sum[k]=sum[ls[k]]+sum[rs[k]];
}
void merge(int &x,int &y){
	if (x==0) return;
	if (x!=0 && y==0){
		y=x; return;
	}
	sum[y]+=sum[x];
	merge(ls[x],ls[y]);
	merge(rs[x],rs[y]);
}
int gfa(int x){
	return (x==fa[x])?x:(fa[x]=gfa(fa[x]));
}
int quiz(int x,int k){
	x=head[gfa(x)];
	if (sum[x]<k) return -1;
	
	int l=1,r=n;
	while (l<r){
		int tmp=sum[ls[x]],mid=(l+r)>>1;
		if (k<=tmp) r=mid,x=ls[x];
		else k-=tmp,l=mid+1,x=rs[x];
	}
	return id[l];
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		fa[i]=i;
		id[a[i]]=i;
		set_up(head[i],a[i],1,n);
	}
	
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		x=gfa(x),y=gfa(y);
		if (x!=y){
			fa[x]=y;
			merge(head[x],head[y]);
		}
	}
	
	scanf("%d",&p);
	for (int i=1;i<=p;i++){
		for (ch=getchar();ch!='Q' && ch!='B';ch=getchar());
		scanf("%d%d",&x,&y);
		if (ch=='B'){
			x=gfa(x),y=gfa(y);
			if (x!=y){
				fa[x]=y;
				merge(head[x],head[y]);
			}
		}
		if (ch=='Q')
			printf("%d\n",quiz(x,y));
	}
	
	return 0;
}