BZOJ 2733: [HNOI2012]永无乡

Description

永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号。

Input

输入文件第一行是用空格隔开的两个正整数 n 和 m,分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数,依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi,表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作,该部分的第一行是一个正整数 q, 表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000

对于 100%的数据 n≤100000,m≤n,q≤300000

Output

对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表 示所询问岛屿的编号。如果该岛屿不存在,则输出-1。

Sample Input

5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

Sample Output

-1
2
5
1
2

Solution

和这题类似[ONTAK2010]Peaks。不用排序啦,直接搞起。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
char getop() {
    char c;
    while (true) {
    	c = getchar();
    	if (c == 'Q') return 'Q';
		if (c == 'B') return 'B';
	}
}
const int maxn = 100005;
const int maxm = 300005;
int siz[maxn], root[maxn], F[maxn], val[maxn], c[maxn][2], fa[maxn];
void pu(int x) {
	siz[x] = 1;
	if (c[x][0]) siz[x] += siz[0]];
	if (c[x][1]) siz[x] += siz[1]];
}
void rotate(int x) {
	int y = fa[x], z = fa[y], a = c[y][1]==x, b = a ^ 1;
	if (z) c[z][1]==y] = x;
	fa[x] = z; fa[y] = x; fa[b]] = y;
	c[y][a] = c[x][b]; c[x][b] = y;
	fa[0] = 0; pu(y); pu(x);
}
int splay(int x) {
	while (fa[x]) {
		int y = fa[x], z = fa[y];
		if (z) {
			if (c[y][0] == x ^ c[z][0] == y) rotate(x);
			rotate(y);
		}
		rotate(x);
	}
	return x;
}
int insert(int &x, int y, int father) {
	if (!x) {
		x = y;
		fa[y] = father;
		return splay(y);
	}
	if (val[y] < val[x]) return insert(c[x][0], y, x);
	return insert(c[x][1], y, x);
}
void dfs_merge(int x, int y) {
	if (c[x][0]) { dfs_merge(c[x][0], y); c[x][0] = 0; }
	if (c[x][1]) { dfs_merge(c[x][1], y); c[x][1] = 0; }
	root[y] = insert(root[y], x, 0);
}
int find(int x) {
	return x == F[x] ? x : F[x] = find(F[x]);
}
int n, m;
int query(int x, int k) {
	int l = c[x][0], ls = siz[l];
	if (k == ls + 1) return x;
	if (k <= ls) return query(l, k);
	return query(c[x][1], k - ls - 1);
}
int main() {
	n = getint(); m = getint();
	int a, b;
	for (int i = 1; i <= n; ++i) {
		val[i] = getint();
		root[i] = i;
		F[i] = i;
		siz[i] = 1;
	}
	for (int i = 1; i <= m; ++i) {
		a = find(getint()); b = find(getint());
		if (siz[root[a]] < siz[root[b]]) swap(a, b);
		dfs_merge(root[b], a);
		F[b] = a;
	}
	int T = getint(), x, y;
	while (T--) {
		if (getop() == 'Q') {
			x = getint(); y = getint(); a = root[find(x)];
			if (siz[a] < y) puts("-1");
			else printf("%d\n", query(root[a], y));
		} else {
			a = find(getint()); b = find(getint());
			if (siz[root[a]] < siz[root[b]]) swap(a, b);
			dfs_merge(root[b], a);
			F[b] = a;
		}
	}
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据