题意：多次求从点x出发经过边权不超过k的边能走到的点中第k大的权值。
解：离线排序 + 并查集 + 线段树合并。
题面有锅...是第k大的权值不是第k大的山。
#include <cstdio>
#include <algorithm> const int N = , M = , V = ; struct Edge {
int x, y, h;
inline bool operator <(const Edge &w) const {
return h < w.h;
}
}edge[M]; struct Ask {
int x, h, k, id;
inline bool operator <(const Ask &w) const {
return h < w.h;
}
}ask[M]; int fa[N], rt[N], ls[V], rs[V], sum[V], siz[N], tot, ans[M], X[N], val[N]; int find(int x) {
if(x == fa[x]) {
return x;
}
return fa[x] = find(fa[x]);
} int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
int o = ++tot;
sum[o] = sum[x] + sum[y];
ls[o] = merge(ls[x], ls[y]);
rs[o] = merge(rs[x], rs[y]);
return o;
} int query(int k, int l, int r, int o) {
if(l == r) {
return r;
}
int mid = (l + r) >> ;
if(k > sum[rs[o]]) {
return query(k - sum[rs[o]], l, mid, ls[o]);
}
else {
return query(k, mid + , r, rs[o]);
}
} inline void Xmerge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) {
return;
}
fa[y] = x;
siz[x] += siz[y];
// printf("siz %d += %d = %d \n", x, siz[y], siz[x]);
rt[x] = merge(rt[x], rt[y]);
return;
} void insert(int p, int l, int r, int &o) {
if(!o) {
o = ++tot;
}
sum[o] = ;
if(l == r) {
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
insert(p, l, mid, ls[o]);
}
else {
insert(p, mid + , r, rs[o]);
}
return;
} int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
X[i] = val[i];
}
std::sort(X + , X + n + );
int xx = std::unique(X + , X + n + ) - X - ;
for(int i = ; i <= n; i++) {
val[i] = std::lower_bound(X + , X + xx + , val[i]) - X;
insert(val[i], , xx, rt[i]);
fa[i] = i; siz[i] = ;
}
for(int i = ; i <= m; i++) {
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].h);
}
for(int i = ; i <= q; i++) {
scanf("%d%d%d", &ask[i].x, &ask[i].h, &ask[i].k);
ask[i].id = i;
}
std::sort(edge + , edge + m + );
std::sort(ask + , ask + q + ); int p = ;
for(int i = ; i <= q; i++) {
while(p <= m && edge[p].h <= ask[i].h) {
Xmerge(edge[p].x, edge[p].y);
p++;
// printf("Xmerge %d %d \n", edge[p].x, edge[p].y);
}
int x = find(ask[i].x);
// printf("x = %d \n", x);
// printf("%d < %d \n", siz[x], ask[i].k);
if(siz[x] < ask[i].k) ans[ask[i].id] = -;
else ans[ask[i].id] = X[query(ask[i].k, , xx, rt[x])];
}
for(int i = ; i <= q; i++) {
printf("%d\n", ans[i]);
}
return ;
}
AC代码