2733: [HNOI2012]永无乡

题意：加边，询问一个连通块中k小值

---

终于写了一下splay启发式合并

本题直接splay上一个节点对应图上一个点就可以了

并查集维护连通性

合并的时候，把size小的树的所有节点插入到size大的中，每个点最多插入log次，复杂度\(O(nlogn*insert\ time)\)

然后主席说如果按照顺序插入，插入的复杂度均摊\(O(1)\)，总的复杂度\(O(nlogn)\)，随便中序遍历一下就有序了.貌似并没有更快

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define lc t[x].ch[0]

#define rc t[x].ch[1]

#define pa t[x].fa

const int N=1e5+5;

inline int read(){

	char c=getchar();int x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int n, m, val[N], x, y, Q; char s[5];

int fa[N];

inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

struct SplayTree{

	struct meow{

		int ch[2], fa, size, v;

	}t[N];

	int sz, root;

	inline void ini() {

		for(int i=1; i<=n; i++) t[i].v=val[i], t[i].size=1;

	}

	inline int wh(int x) {return t[pa].ch[1] == x;}

	inline void update(int x) {t[x].size = t[lc].size + t[rc].size + 1;}

	inline void rotate(int x) {

		int f=t[x].fa, g=t[f].fa, c=wh(x);

		if(g) t[g].ch[wh(f)]=x; t[x].fa=g;

		t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa=f;

		t[x].ch[c^1]=f; t[f].fa=x;

		update(f); update(x);

	}

	inline void splay(int x, int tar) {

		for(; pa!=tar; rotate(x))

			if(t[pa].fa != tar) rotate(wh(x)==wh(pa) ? pa : x);

		if(tar==0) root=x;

	}

	inline void insert(int p) {

		int x=root, f=0, v=t[p].v;

		while(x) f=x, x= v<t[x].v ? lc : rc;

		x=p;

		t[f].ch[v>t[f].v]=x; t[x].fa=f;

		splay(x, 0);

	}

	int q[N], p;

	void order(int x) {

		int l=lc, r=rc;

		lc=rc=pa=0; t[x].size=1;

		if(l) order(l);

		insert(x);

		if(r) order(r);

	}

	void Merge(int x, int y) {

		if(x==y) return;

		splay(x, 0); splay(y, 0);

		if(t[x].size > t[y].size) swap(x, y);

		fa[x]=y; root=y;

		order(x);

	}

	int kth(int x, int k) {

		splay(x, 0); int lsize=0;

		while(x) {

			int _=lsize+t[lc].size;

			if(k<=_) x=lc;

			else if(k==_+1) return x;

			else lsize=_+1,x=rc;

		}

		return -1;

	}

}S;

int main() {

	freopen("in","r",stdin);

	n=read(); m=read();

	for(int i=1; i<=n; i++) val[i]=read(), fa[i]=i;

	S.ini();

	for(int i=1; i<=m; i++) x=find(read()), y=find(read()), S.Merge(x, y);

	Q=read();

	for(int i=1; i<=Q; i++) {

		scanf("%s",s); x=find(read()); y=read();

		if(s[0]=='B') y=find(y), S.Merge(x, y);

		else printf("%d\n", S.kth(x, y));

	}

}