[ONTAK2010]Peaks

kruskal重构树练手题。

LG传送门竟然不强制在线？看到离线水过很不爽：B站强制在线版传送门

看到“询问从点\(v\)开始只经过困难值小于等于\(x\)的路径”，马上想到kruskal重构树。先把重构树搞出来，可以先用类似NOI2018归程（题解）的方法处理，然后把叶子节点按dfs序放到序列上，重构树上每个点的子树的叶子节点在序列上是连续的，预处理出每个点的子树在序列上对应的左右端点，问题就变成了静态区间第\(k\)大，直接主席树。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 200003, M = 500003;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int a[N], b[N], f[N], rot[N], dep[N], fa[N][20], son[N][2], val[N], id[N], l[N], r[N], n, tim, T;

struct edge { int u, v, w; }g[M];

struct segtree { int p, q, s; }e[N << 5];

I int operator < (edge x, edge y) { return x.w < y.w; }

I int find(int x) {

    R int r = x, y;

    while (f[r] ^ r)

        r = f[r];

    while (x ^ r)

        y = f[x], f[x] = r, x = y;

    return r;

}

void dfs(int x) {

    dep[x] = dep[fa[x][0]] + 1;

    for (R int i = 1; i < 20; ++i)

        fa[x][i] = fa[fa[x][i - 1]][i - 1];

    if (x <= n) {

        id[++tim] = x, l[x] = r[x] = tim;

        return ;

    }

    dfs(son[x][0]), dfs(son[x][1]), l[x] = l[son[x][0]], r[x] = r[son[x][1]];

}

void build(int &k, int l, int r) {

    k = ++T;

    if (l == r)

        return ;

    R int m = l + r >> 1;

    build(e[k].p, l, m), build(e[k].q, m + 1, r);

}

int modify(int k, int l, int r, int x) {

    R int t = ++T;

    e[t].p = e[k].p, e[t].q = e[k].q, e[t].s = e[k].s + 1;

    if (l == r)

        return t;

    R int m = l + r >> 1;

    if (x <= m)

        e[t].p = modify(e[k].p, l, m, x);

    else

        e[t].q = modify(e[k].q, m + 1, r, x);

    return t;

}

int query(int k, int t, int l, int r, int x) {

    if (l == r)

        return x <= e[t].s - e[k].s ? l : -1;

    R int m = l + r >> 1, y = e[e[t].q].s - e[e[k].q].s;

    if (x > y)

        return query(e[k].p, e[t].p, l, m, x - y);

    else

        return query(e[k].q, e[t].q, m + 1, r, x);

}

int main() {

    R int S, m, Q, i, x, y, z, cnt;

    cnt = n = rd(), m = rd(), Q = rd();

    for (i = 1; i <= n; ++i)

        f[i] = i, a[i] = b[i] = rd();

    sort(b + 1, b + n + 1), S = unique(b + 1, b + n + 1) - b - 1, build(rot[0], 1, S);

    for (i = 1; i <= m; ++i)

        g[i] = (edge){rd(), rd(), rd()};

    sort(g + 1, g + m + 1);

    for (i = 1; i <= m; ++i) {

        x = find(g[i].u), y = find(g[i].v);

        if (x ^ y) {

            val[++cnt] = g[i].w, f[cnt] = f[x] = f[y] = cnt;

            son[cnt][0] = x, son[cnt][1] = y, fa[x][0] = fa[y][0] = cnt;

        }

    }

    dfs(cnt);

    for (i = 1; i <= n; ++i)

        rot[i] = modify(rot[i - 1], 1, S, lower_bound(b + 1, b + S + 1, a[id[i]]) - b);

    while (Q--) {

        x = rd(), y = rd(), z = rd();

        for (i = 19; ~i; --i)

            if (dep[x] - (1 << i) > 0 && val[fa[x][i]] <= y)

                x = fa[x][i];

        z = query(rot[l[x] - 1], rot[r[x]], 1, S, z);

        printf("%d\n", ~z ? b[z] : -1);

    }

    return 0;

}