【题解】bzoj#3545 Peaks

有 $n$ 座山峰,每座山峰有他的高度 $h_i$。

有山峰之间有双向道路相连,共 $m$ 条路径,每条路径有一个困难值。

现在有 $q$ 组询问,询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰,如果无解输出 $-1$。

发现可以倍增,因为 $\leq x$ 的权在重构树上是一个子树。

倍增完了就可以直接套主席树了。主席树可以比较简单的按照叶子的标号建,每个边结点维护一个 $\rm leftrange$ 和 $\rm rightrange$ 即可。

等会儿,我就整理这么点儿东西为啥要新开这一篇blog啊?太浪费资源了吧QAQ。

那看上去就只能用代码来占空间了

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
106
107
108
109
110
111
112
113
114
115
using namespace std ;

#define to(k) E[k].to
#define fr(k) E[k].fr
#define val(k) E[k].val
#define next(k) E[k].next

const int N = 500010 ;
const int M = 500010 ;
const int V = 5000010 ;

struct Edge{
int fr, to ;
int next, val ;
}E[N << 1] ;
int head[N], cnt ;

int len ;
int dad[N] ;
int wth[N] ;
int n, m, q ;
int rg[N][2] ;
int fa[N][20] ;
int base[N], t[N] ;

int sum[V], res, sz ;
int rt[V], lc[V], rc[V] ;

int build(int l, int r){
int now = ++ sz ;
if (l == r) return now ;
int mid = (l + r) >> 1 ;
lc[now] = build(l, mid) ;
rc[now] = build(mid + 1, r) ;
return now ;
}
int update(int last, int l, int r, int v){
int now = ++ sz ;
lc[now] = lc[last] ;
rc[now] = rc[last] ;
sum[now] = sum[last] + 1 ;
int mid = (l + r) >> 1 ;
if (l == r) return now ;
if (v <= mid)
lc[now] = update(lc[last], l, mid, v) ;
else rc[now] = update(rc[last], mid + 1, r, v) ;
return now ;
}
int query(int rtl, int rtr, int l, int r, int v){
if (l == r) return l ;
int mid = (l + r) >> 1 ;
int delta = sum[rc[rtr]] - sum[rc[rtl]] ;
if (v > delta)
return query(lc[rtl], lc[rtr], l, mid, v - delta) ;
else return query(rc[rtl], rc[rtr], mid + 1, r, v) ;
}
void add(int u, int v, int w){
to(++ cnt) = v ;
val(cnt) = w, fr(cnt) = u ;
next(cnt) = head[u], head[u] = cnt ;
}
int find(int x){
return x == dad[x] ? x : dad[x] = find(dad[x]) ;
}
bool comp(Edge A, Edge B){ return A.val < B.val ; }
void dfs(int u){
//cout << u << endl ;
for (int i = 1 ; i <= 18 ; ++ i)
fa[u][i] = fa[fa[u][i - 1]][i - 1] ;
rg[u][0] = res ;
if (!head[u])
rg[u][0] = ++ res,
rt[res] = update(rt[res - 1], 1, len, base[u]) ;
for (int k = head[u] ; k ; k = next(k)) dfs(to(k)) ;
rg[u][1] = res ;
}
int main(){
cin >> n >> m >> q ;
int u, v, w, now, k, tot, op ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), t[i] = base[i] ;
sort(t + 1, t + n + 1) ;
len = unique(t + 1, t + n + 1) - t - 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = lower_bound(t + 1, t + len + 1, base[i]) - t ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w) ;
sort(E + 1, E + cnt + 1, comp) ;
for (int i = 1 ; i <= 2 * n ; ++ i) dad[i] = i ;
fill(head + 1, head + n + 1, 0), op = cnt, tot = n, cnt = 0 ;
for (int i = 1 ; i <= op ; ++ i){
int f1 = find(fr(i)) ;
int f2 = find(to(i)) ;
if (f1 != f2){
now = ++ tot ;
wth[now] = val(i) ;
dad[f1] = dad[f2] = now ;
fa[f1][0] = fa[f2][0] = now ;
add(now, f1, 0),add(now, f2, 0) ;
}
}
//cout << tot << endl ;
//for (int i = 1 ; i <= tot ; ++ i) cout << fa[i][0] << endl ;
rt[0] = build(1, len) ; dfs(now) ; //cout << res << endl ;
for (int i = 1 ; i <= q ; ++ i){
scanf("%d%d%d", &u, &w, &k) ;
for (int j = 18 ; j >= 0 ; -- j)
if (fa[u][j] && wth[fa[u][j]] <= w) u = fa[u][j] ;
//cout << u << endl ;
if (rg[u][1] - rg[u][0] < k) puts("-1") ;
//cout << rg[u][0] << " " << rg[u][1] << endl ;
else printf("%d\n", t[query(rt[rg[u][0]], rt[rg[u][1]], 1, len, k)]) ;
}
return 0 ;
}