P4197 Peaks 题解
题目描述
在 Bytemountains 有 \(n\) 座山峰，每座山峰有他的高度 \(h_i\)。有些山峰之间有双向道路相连，共 \(m\) 条路径，每条路径有一个困难值，这个值越大表示越难走。
现在有 \(q\) 组询问，每组询问询问从点 \(v\) 开始只经过困难值小于等于 \(x\) 的路径所能到达的山峰中第 \(k\) 高的山峰，如果无解输出 \(-1\)。
对于 \(100\%\) 的数据，\(n \le 10^5\)，\(0 \le m,q \le 5\times 10^5\)，\(h_i,c,x \le 10^9\)。
思路
由于有最大瓶颈路的限制，考虑 \(\text{Kruskal}\) 重构树，如果我们当前已经构建出了这张图的 重构树，观察发现，从点 \(v\) 开始只经过最大边权 \(\le x\) 的边等价于找到 \(v\) 最浅的虚点祖先 \(u\) 满足其点权 \(\le x\)，那么 \(v\) 每次可以到达的点都只能是 \(u\) 点控制的点，也就是其子孙。
一个虚点的子孙在 \(\text{dfn}\) 序上一定是一段连续的区间，问题就转化为了区间第 \(k\) 大，用主席树维护即可。
时间复杂度：\(O(m\log m + n\log n + q\log n)\)，这是在线算法，有一个双倍经验嘿嘿嘿。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10;
int n, m, q, h[N];
struct qwq {
int a, b, c;
bool operator < (const qwq &W) const {
return c < W.c;
}
} e[N];
int fa[N], idx;
vector<int> g[N];
qwq p[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal() {
sort(e + 1, e + m + 1);
idx = n;
for(int i = 1; i <= m; i ++) {
int x = find(e[i].a), y = find(e[i].b);
if(x == y) continue;
g[++ idx].push_back(x), g[idx].push_back(y), fa[idx] = idx;
p[idx].c = e[i].c;
fa[x] = idx, fa[y] = idx;
}
}
int f[N][23];
int pos[N], awa, dfn[N];
void dfs(int u) {
if(g[u].size() == 0) pos[u] = ++ awa, dfn[awa] = u, p[u].a = p[u].b = awa;
else p[u].a = 1e9;
for(auto v : g[u]) {
f[v][0] = u;
for(int i = 1; i <= 22; i ++) f[v][i] = f[f[v][i - 1]][i - 1];
dfs(v);
p[u].a = min(p[v].a, p[u].a), p[u].b = max(p[u].b, p[v].b);
}
}
int getfa(int u, int x) {
for(int i = 22; i >= 0; i --)
if(f[u][i] && p[f[u][i]].c <= x)
u = f[u][i];
return u;
}
int dat[N << 4], ls[N << 4], rs[N << 4], tot, root[N];
int update(int q, int l, int r, int x) {
int p = ++ tot;
int mid = l + r >> 1;
dat[p] = dat[q], ls[p] = ls[q], rs[p] = rs[q];
if(l == r && x == l) return dat[p] ++, p;
if(x <= mid) ls[p] = update(ls[q], l, mid, x);
else rs[p] = update(rs[q], mid + 1, r, x);
dat[p] = dat[ls[p]] + dat[rs[p]];
return p;
}
int query(int p, int q, int l, int r, int k) {
if(l == r) return l;
int c = dat[rs[q]] - dat[rs[p]];
int mid = l + r >> 1;
if(k <= c) return query(rs[p], rs[q], mid + 1, r, k);
else return query(ls[p], ls[q], l, mid, k - c);
}
int disc[N], cnt;
int get(int x) {
return lower_bound(disc + 1, disc + cnt + 1, x) - disc;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++) cin >> h[i], fa[i] = i, disc[i] = h[i];
sort(disc + 1, disc + n + 1);
cnt = unique(disc + 1, disc + n + 1) - disc - 1;
for(int i = 1; i <= m; i ++) cin >> e[i].a >> e[i].b >> e[i].c;
kruskal();
dfs(idx);
for(int i = 1; i <= awa; i ++)
root[i] = update(root[i - 1], 1, cnt, get(h[dfn[i]]));
int a, b, c, t;
while(q --) {
cin >> a >> b >> c;
t = getfa(a, b);
if(p[t].b - p[t].a + 1 < c) {
cout << -1 << '\n';
continue;
}
cout << disc[query(root[p[t].a - 1], root[p[t].b], 1, cnt, c)] << '\n';
}
return 0;
}