[HNOI2012]永无乡

题目描述

永无乡包含 \(n\) 座岛，编号从 \(1\) 到 \(n\) ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 \(n\) 座岛排名，名次用 \(1\) 到 \(n\) 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 \(a\) 出发经过若干座（含 \(0\) 座）桥可以到达岛 \(b\) ，则称岛 \(a\) 和岛 \(b\) 是连通的。

现在有两种操作：

B x y 表示在岛 \(x\) 与岛 \(y\) 之间修建一座新桥。

Q x k 表示询问当前与岛 \(x\) 连通的所有岛中第 \(k\) 重要的是哪座岛，即所有与岛 \(x\) 连通的岛中重要度排名第 \(k\) 小的岛是哪座，请你输出那个岛的编号。

输入格式

第一行是用空格隔开的两个整数，分别表示岛的个数 \(n\) 以及一开始存在的桥数 \(m\)。

第二行有 \(n\) 个整数，第 \(i\) 个整数表示编号为 \(i\) 的岛屿的排名 \(p_i\)。

接下来 \(m\) 行，每行两个整数 \(u, v\)，表示一开始存在一座连接编号为 \(u\) 的岛屿和编号为 \(v\) 的岛屿的桥。

接下来一行有一个整数，表示操作个数 \(q\)。

接下来 \(q\) 行，每行描述一个操作。每行首先有一个字符 \(op\)，表示操作类型，然后有两个整数 \(x, y\)。

若 \(op\) 为 Q，则表示询问所有与岛 \(x\) 连通的岛中重要度排名第 \(y\) 小的岛是哪座，请你输出那个岛的编号。
若 \(op\) 为 B，则表示在岛 \(x\) 与岛 \(y\) 之间修建一座新桥。

输出格式

对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 \(-1\) 。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 \(20\%\) 的数据，保证 \(n \leq 10^3\), \(q \leq 10^3\)。
对于 \(100\%\) 的数据，保证 \(1 \leq m \leq n \leq 10^5\), \(1 \leq q \leq 3 \times 10^5\)，\(p_i\) 为一个 \(1 \sim n\) 的排列，\(op \in \{\texttt Q, \texttt B\}\)，\(1 \leq u, v, x, y \leq n\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define lid (tree[id].lson)
#define rid (tree[id].rson)

using namespace std;

int n, m, q, tot, val[5211314];
int fa[5211314];
int root[5211314];

struct Segment_Tree {
	int lson, rson;
	int sum;
	int Rank;
}tree[5211314];

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch - '0');
		ch = getchar();
	}
	return x * f;
}

struct DisjointSetUnion {
	int Find(int x) {
		if (fa[x] == x) return x;
		else return fa[x] = Find(fa[x]);
	}
	bool Check(int x, int y) {
		if (Find(x) == Find(y)) return true;
		else return false;
	} 
}dsu;

struct MergeSegmentTree {
	inline void PushUp(int id) {
		tree[id].sum = tree[lid].sum + tree[rid].sum;
		return;
	}
	void Update(int &id, int l, int r, int pos, int ans) {
		if (id == 0) id = ++ tot;
		if (l == r) {
			tree[id].sum = 1;
			tree[id].Rank = ans;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) Update(lid, l, mid, pos, ans);
		else Update(rid, mid + 1, r, pos, ans);
		PushUp(id);
		return;
	}
	int Merge(int a, int b, int l, int r) {
		if (a == 0) return b;
		if (b == 0) return a;
		if (l == r) {
			tree[a].sum += tree[b].sum;
			tree[a].Rank = tree[b].Rank;
			return a;
		}
		int mid = (l + r) >> 1;
		tree[a].lson = Merge(tree[a].lson, tree[b].lson, l, mid);
		tree[a].rson = Merge(tree[a].rson, tree[b].rson, mid + 1, r);
		PushUp(a);
		return a;
	}
	int Query(int id, int l, int r, int k) {
		int mid = (l + r) >> 1, ans;
		if (tree[id].sum < k || id == 0) return 0;
		if (l == r) return tree[id].Rank;
		if (k <= tree[lid].sum) ans = Query(lid, l, mid, k);
		else ans = Query(rid, mid + 1, r, k - tree[lid].sum);
		return ans;
	}
}ask;

inline void Union(int u, int v) {
	u = dsu.Find(u);
	v = dsu.Find(v);
	if (u == v) return;
	root[u] = ask.Merge(root[u], root[v], 1, n);
	fa[v] = u;
	return;
}

int main() {
	n = read();
	m = read();
	for (int i = 1; i <= n; ++ i) {
		val[i] = read();
		fa[i] = i;
		ask.Update(root[i], 1, n, val[i], i);
	}
	for (int i = 1, u, v; i <= m; ++ i) {
		u = read(), v = read();
		Union(u, v);
	}
	q = read();
	for (int i = 1, x, y; i <= q; ++ i) {
		char ch = getchar();
		while (ch != 'Q' && ch != 'B') {
			ch = getchar();
		}
		x = read();
		y = read();
		if (ch == 'B') {
			Union(x, y);
		}
		else {
			x = dsu.Find(x);
			//注意这里一定要用find(x)的而不是fa[x]的值
			//因为这里的x可能刚更新过,fa[x]的值不是合并后线段树的根节点的值
			if (tree[root[x]].sum < y) printf("-1\n");
			else {
				printf("%d\n", ask.Query(root[x], 1, n, y));
			}
		}
	}
	return 0;
}