BZOJ3545【ONTAK2010】Peaks <并查集+线段树合并>

Problem

【ONTAK2010】Peaks

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

Bytemountains\mathrm{Bytemountains}NN座山峰,每座山峰有他的高度hih_i
有些山峰之间有双向道路相连,共MM条路径,每条路径有一个困难值,这个值越大表示越难走。
现在有QQ组询问,每组询问询问从点vv开始只经过困难值小于等于xx的路径所能到达的山峰中第kk高的山峰,如果无解输出1-1

Input

第一行三个数N,M,QN,M,Q
第二行NN个数,第ii个数为hih_i
接下来MM行,每行33个数a  b  ca\;b\;c,表示从aabb有一条困难值为cc的双向路径。
接下来QQ行,每行三个数v  x  kv\;x\;k,表示一组询问。

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
6
1
-1
8

HINT

N105N\le10^5M,Q5×105M,Q\le5\times10^5hi,c,x109h_i,c,x\le10^9

Source

By Sbullet

标签:并查集 线段树合并

Solution

离线询问,按xx从小到大排序,发现是裸的线段树合并。
MM条边按照边权从小到大排序,按xx从小到大处理询问,每次只需要加边而不需要删边。这时就和BZOJ2733【HNOI2012】永无乡一样了。用并查集维护联通关系,每个连通块内用权值线段树维护。若某条边使得两个块不联通的块联通,则合并连个块的线段树,查询则直接在块内查询即可。

其实可以在线做,详见BZOJ3551【ONTAK2010】Peaks加强版。

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
#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 500000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int N, M, Q, sz, h[MAX_N+5];
int fa[MAX_N+5], rt[MAX_N+5], ans[MAX_M+5];
int val[MAX_N+5], rev[MAX_N+5], tot; map <int, int> mp;
struct edge {int u, v, c;} E[MAX_M+5];
struct node {int ls, rs, s;} tr[MAX_N*50];
struct quest {int id, u, c, k;} q[MAX_M+5];
bool cmpe(const edge &a, const edge &b) {return a.c < b.c;}
bool cmpq(const quest &a, const quest &b) {return a.c < b.c;}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void modify(int &v, int s, int t, int p) {
if (!v) v = ++sz; if (s == t) {tr[v].s++; return;}
if (p <= mid) modify(tr[v].ls, s, mid, p);
if (p >= mid+1) modify(tr[v].rs, mid+1, t, p);
tr[v].s = tr[tr[v].ls].s+tr[tr[v].rs].s;
}
int query(int v, int s, int t, int k) {
if (s == t) return s; int rsz = tr[tr[v].rs].s;
if (rsz < k) return query(tr[v].ls, s, mid, k-rsz);
return query(tr[v].rs, mid+1, t, k);
}
int merge(int x, int y) {
if (!x) return y; if (!y) return x;
tr[x].s = tr[x].s+tr[y].s;
tr[x].ls = merge(tr[x].ls, tr[y].ls);
tr[x].rs = merge(tr[x].rs, tr[y].rs);
return x;
}
int main() {
read(N), read(M), read(Q);
for (int i = 1; i <= N; i++) fa[i] = i;
for (int i = 1; i <= N; i++) read(h[i]);
for (int i = 1; i <= N; i++) val[i] = h[i];
sort(val+1, val+N+1);
for (int i = 1; i <= N; i++)
if (i == 1 || (val[i]^val[i-1]))
mp[val[i]] = ++tot, rev[tot] = val[i];
for (int i = 1; i <= N; i++) h[i] = mp[h[i]];
for (int i = 1; i <= N; i++) modify(rt[i], 1, N, h[i]);
for (int i = 1, u, v, c; i <= M; i++)
read(u), read(v), read(c), E[i] = (edge){u, v, c};
for (int i = 1, u, c, k; i <= Q; i++)
read(u), read(c), read(k), q[i] = (quest){i, u, c, k};
sort(E+1, E+M+1, cmpe), sort(q+1, q+Q+1, cmpq);
for (int i = 1, j = 1, lft = N-1; i <= Q; i++) {
for (int u, v; lft && j <= M && E[j].c <= q[i].c; j++)
if ((u = getf(E[j].u)) ^ (v = getf(E[j].v)))
fa[v] = u, rt[u] = merge(rt[u], rt[v]), lft--;
int v = rt[getf(q[i].u)];
if (tr[v].s < q[i].k) ans[q[i].id] = -1;
else ans[q[i].id] = rev[query(v, 1, N, q[i].k)];
}
for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
return 0;
}