P4197 Peaks

P4197 Peaks

Meaning

在一张有向无环图上，每个点有权值 $h$，每条边有长度 $w$。每次询问以 $u$ 作为起点只经过长度不大于 $x$ 的边所能到达的点中第 $k$ 大的点权。

Sol

考虑按照边权从小到大构建 Kruskal 树，然后树上倍增找到通过边权不大于 $x$ 所能到达的连通子树的根节点，然后按照 dfn 序构建主席树，即可实现在线查询。

Detail

1. 离散化后要将权值带回；
2. 总结：码力太差。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
const int inf = 1e9 + 1e7, MAXN = 6e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct edge {
    int u, v, w;
    bool friend operator <(const edge &A, const edge &B) {
        return B.w > A.w;
    }
} c[MAXN];
struct Node { int ls, rs, sz; } ;
struct Edge { int nxt, to; } e[MAXN << 2];
int head[MAXN], dfnw[MAXN], ffa[MAXN][20], dfn[MAXN], rt[MAXN], sz[MAXN], fa[MAXN], to[MAXN], ph[MAXN], th[MAXN], f[MAXN], h[MAXN];
int n, m, q, len, tot, cnt, dfncnt, nodecnt;

void Addedge(int u, int v) { e[++ tot] = (Edge){head[u], v}, head[u] = tot; return ; }

int Find(int x) { return (fa[x] == x ? x : fa[x] = Find(fa[x])); }

void Disc(void) {
    for (int i = 1; i <= n; i ++) ph[i] = h[i];
    sort(ph + 1, ph + n + 1);
    len = unique(ph + 1, ph + n + 1) - ph - 1;
    for (int i = 1; i <= n; i ++) th[i] = lower_bound(ph + 1, ph + len + 1, h[i]) - ph;
    for (int i = 1; i <= n; i ++) to[th[i]] = h[i];
    return ;
}

void Dfs(int u) {
    dfn[u] = inf;
    for (int i = 1; i <= 19; i ++) ffa[u][i] = ffa[ffa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (ffa[u][0] == v) continue ; ffa[v][0] = u;
        Dfs(v), dfn[u] = min(dfn[v], dfn[u]), sz[u] += sz[v];
    }
    if(dfn[u] == inf) dfn[u] = ++ dfncnt, sz[u] = 1, dfnw[dfn[u]] = th[u];
    return ;
}

struct PW_SegmentTree {
    Node tree[MAXN * 20];

    void Insert(int l, int r, int p, int u, int &x) {
        x = ++ nodecnt, tree[x].sz = tree[u].sz + 1;
        if (l == r) ;
        else {
            int mid = l + r >> 1;
            if (p <= mid) rs(x) = rs(u), Insert(l, mid, p, ls(u), ls(x));
            else ls(x) = ls(u), Insert(mid + 1, r, p, rs(u), rs(x));
        }
        return ;
    }

    int Query(int l, int r, int k, int u, int x) {
        if (l == r) return l;
        int mid = l + r >> 1, del = tree[ls(x)].sz - tree[ls(u)].sz;
        return (k <= del ? Query(l, mid, k, ls(u), ls(x)) : Query(mid + 1, r, k - del, rs(u), rs(x)));
    }
} pwst;

int main(void) {

    cnt = n = readint, m = readint, q = readint;
    for (int i = 1; i <= n; i ++) fa[i] = i;
    for (int i = 1; i <= n; i ++) h[i] = readlint;
    for (int i = 1; i <= m; i ++) {
        int u = readint, v = readint, w = readint;
        c[i] = (edge){u, v, w};
    }
    sort(c + 1, c + m + 1), Disc();
    for (int i = 1; i <= n; i ++) f[i] = th[i];
    for (int i = 1; i <= m; i ++) {
        int u = c[i].u, v = c[i].v, w = c[i].w, fu = Find(u), fv = Find(v);
        if (fu == fv) continue ;
        f[++ cnt] = w, fa[cnt] = fa[fu] = fa[fv] = cnt;
        Addedge(cnt, fu), Addedge(cnt, fv), Addedge(fu, cnt), Addedge(fv, cnt);
    }
    Dfs(cnt);
    for (int i = 1; i <= dfncnt; i ++) pwst.Insert(1, len, dfnw[i], rt[i - 1], rt[i]);
    while (q --) {
        int u = readint, x = readint, k = readint;
        for (int i = 19; i >= 0; i --) if (ffa[u][i] && f[ffa[u][i]] <= x) u = ffa[u][i];
        if (k > sz[u]) puts("-1");
        else printf("%d\n", to[pwst.Query(1, len, sz[u] - k + 1, rt[dfn[u] - 1], rt[dfn[u] + sz[u] - 1])]);
    }

    return 0;
}