OI

BZOJ 3545: [ONTAK2010]Peaks

Description

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

Input

第一行三个数N，M，Q。

第二行N个数，第i个数为h_i

接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。

接下来Q行，每行三个数v x k，表示一组询问。

Output

对于每组询问，输出一个整数表示答案。

Sample Input

10 11 4

1 2 3 4 5 6 7 8 9 10

1 4 4

2 5 3

9 8 2

7 8 10

7 1 4

6 7 1

6 4 8

2 1 5

10 8 10

3 4 7

3 4 6

1 5 2

1 5 6

1 5 8

8 9 2

Sample Output

6

1

-1

8

HINT

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

Solution

先对询问按照困难值排序，然后相当于求一个联通块内第K大的点。这个我们可以用并查集+平衡树来解决。每个并查集根上挂一颗平衡树，合并的时候启发式合并就可以了。

注意问的是输出高度而不是输出id。。。

蒟蒻平衡树常数巨大，9656ms跑过。。。QAQ

Code

  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

#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;
}
const int maxn = 100005;
const int maxm = 500005;
int fa[maxn], c[maxn][2], siz[maxn], H[maxn], F[maxn], root[maxn];
int A[maxm], B[maxm], C[maxm], V[maxm], X[maxm], K[maxm], ide[maxm], idq[maxm], ans[maxm];
int n, m, q;
bool cmpC(int x, int y) { return C[x] < C[y]; }
bool cmpX(int x, int y) { return X[x] < X[y]; }
int find(int x) { return x == F[x] ? x : F[x] = find(F[x]); }
void pu(int x) {
	siz[x] = 1;
	if (c[x][0]) siz[x] += siz[c[x][0]];
	if (c[x][1]) siz[x] += siz[c[x][1]];
}
void rotate(int x) {
	int y = fa[x], z = fa[y], a = (c[y][1]==x), b = a ^ 1;
	if (z) c[z][c[z][1]==y]=x;
	fa[x] = z; fa[y] = x; fa[c[x][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[z][0]==y ^ c[y][0]==x) rotate(x);
			else 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 (H[y] < H[x]) return insert(c[x][0], y, x);
	else return insert(c[x][1], y, x);
}
int query(int x, int k) {
	int r = c[x][1], rs = siz[r];
	if (k == rs + 1) return x;
	if (k <= rs) return query(r, k);
	else return query(c[x][0], k - rs - 1);
}
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 main() {
	n = getint(); m = getint(); q = getint();
	for (int i = 1; i <= n; ++i) {
		H[i] = getint();
		F[i] = i;
		root[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		A[i] = getint();
		B[i] = getint();
		C[i] = getint();
		ide[i] = i;
	}
	for (int i = 1; i <= q; ++i) {
		V[i] = getint();
		X[i] = getint();
		K[i] = getint();
		idq[i] = i;
	}
	sort(ide+1, ide+1+m, cmpC);
	sort(idq+1, idq+1+q, cmpX);
	int nq, ptr = 0;
	for (int i = 1; i <= q; ++i) {
		nq = idq[i];
		while (ptr < m && C[ide[ptr+1]] <= X[nq]) {
			++ptr;
			int ne = ide[ptr];
			int a = find(A[ne]), b = find(B[ne]);
			if (a != b) {
				if (siz[root[a]] < siz[root[b]]) swap(a, b);
				dfs_merge(root[b], a);
				F[b] = a;
			}
		}
		int rt = root[find(V[nq])];
		if (siz[rt] < K[nq]) ans[nq] = -1;
		else ans[nq] = H[query(rt, K[nq])];
	}
	for (int i = 1; i <= q; ++i)
		printf("%d\n", ans[i]);
    return 0;
}