BZOJ 2733: [HNOI2012]永无乡

oi-forever 2018-06-19 原文

2733: [HNOI2012]永无乡

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4872 Solved: 2617
[Submit][Status][Discuss]

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

总结：

线段树合并板子

对每个联通块建立权值线段树

对于增加一条路径，合并这两颗线段树

并查集维护连通性

查询的话，直接在权值线段树上二分就好了

#include <bits/stdc++.h>
using namespace std;

const int maxn = 120000;
int n, m, Q, tot, a[maxn], f[maxn];
struct Node {
	int ls, rs, v;
} t[maxn << 4]; int rt[maxn];

void Merge(int &r1, int r2) {
	if(!r1) {r1 = r2; return;}
	if(!r2) return;
	t[r1].v += t[r2].v;
	Merge(t[r1].ls, t[r2].ls); Merge(t[r1].rs, t[r2].rs);
}
int find(int x) {
	return f[x] == x ?x :f[x] = find(f[x]);
}
void merge(int u, int v) {
	u = find(u); v = find(v);
	if(u != v) {
		f[v] = u;
		Merge(rt[u], rt[v]);
	}
}
void Modify(int &o, int l, int r, int q) {
	if(!o) o = ++tot; t[o].v++;
	if(l == r) return; int mid = (l + r) >> 1;
	if(q <= mid) Modify(t[o].ls, l, mid, q);
	else Modify(t[o].rs, mid + 1, r, q);
}
int Query(int o, int l, int r, int K) {
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(K <= t[t[o].ls].v) return Query(t[o].ls, l, mid, K);
	else return Query(t[o].rs, mid + 1, r, K - t[t[o].ls].v);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, x; i <= n; ++i) {
		scanf("%d", &x); a[x] = i;
		Modify(rt[f[i] = i], 1, n, x); 
	}
	while(m--) {
		int u, v; scanf("%d%d", &u, &v);
		merge(u, v);
	} scanf("%d", &Q); char ch[5];
	while(Q--) {
		scanf("%s", ch);
		if(ch[0] == 'Q') {
			int x, k; scanf("%d%d", &x, &k);
			x = find(x);
			if(t[rt[x]].v < k) puts("-1");
			else printf("%d\n", a[Query(rt[x], 1, n, k)]);  
		} else {
			int u, v; scanf("%d%d", &u, &v);
			merge(u, v);
		}
	}
	return 0;
}