题目地址：BZOJ：Problem 3545. — [ONTAK2010]Peaks

题目描述

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

题意简述

有一个图，点和边都有权值。回答若干询问，每个询问表示只保留图中边权不大于x的边，v所在的连通块中，点权k大

输入输出格式

输入格式：
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。

输出格式：
对于每组询问，输出一个整数表示答案。

输入输出样例

输入样例#1：

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2

输出样例#1：

6
1
-1
8

说明

【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

题解

首先，连通性可以使用并查集维护。我们可以先对点权离散化，考虑每个连通块维护一个权值线段树，使用动态开点写法，在并查集的代表元处记下根下标。
我们考虑离线解决这个问题，对询问和边都排序，从小到大加边，并启发式合并连通块的线段树。由于线段树规模倍增，启发式合并的复杂度是期望O(\log n)的。因此总复杂度是O(n \log n)的，可以接受。
谁来告诉我为什么我的线段树常数看上去很优秀？这好像已经不是第一次了

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 500005;

int n, m, q;

int fa[MAXN], siz[MAXN];

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

struct Node {
    int lch, rch, val;
} tr[MAXN << 4];
int rt[MAXN], tot;

inline void insert(int &o, int l, int r, int x) {
    if(!o) o = ++tot;
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline int query(int o, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1, rsiz = tr[tr[o].rch].val;
    if(k <= rsiz) return query(tr[o].rch, mid + 1, r, k);
    else return query(tr[o].lch, l, mid, k - rsiz);
}

inline int merge(int o1, int o2) {
    if(!o1) return o2;
    if(!o2) return o1;
    if(!tr[o1].lch && !tr[o1].rch) {
        tr[o1].val += tr[o2].val;
        return o1;
    }
    tr[o1].lch = merge(tr[o1].lch, tr[o2].lch);
    tr[o1].rch = merge(tr[o1].rch, tr[o2].rch);
    tr[o1].val = tr[tr[o1].lch].val + tr[tr[o1].rch].val;
    return o1;
}

int w[MAXN];

std::vector<int> tmp;

struct Edge {
    int u, v, w;
} edges[MAXN];

inline bool cmpE(Edge a, Edge b) {
    return a.w < b.w;
}

struct Query {
    int v, x, k, id;
} qur[MAXN];

inline bool cmpQ(Query a, Query b) {
    return a.x < b.x;
}

int ans[MAXN];

int main() {
    n = readint(); m = readint(); q = readint();
    for(int i = 1; i <= n; i++) {
        fa[i] = i; siz[i] = 1;
    }
    tmp.push_back(-1);
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
        tmp.push_back(w[i]);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i = 1; i <= n; i++) {
        w[i] = std::lower_bound(tmp.begin(), tmp.end(), w[i]) - tmp.begin();
        insert(rt[i], 1, n, w[i]);
    }
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    std::sort(edges + 1, edges + m + 1, cmpE);
    for(int i = 1; i <= q; i++) {
        qur[i].v = readint(); qur[i].x = readint(); qur[i].k = readint(); qur[i].id = i;
    }
    std::sort(qur + 1, qur + q + 1, cmpQ);
    int ne = 1;
    for(int i = 1; i <= q; i++) {
        for(; ne <= m && edges[ne].w <= qur[i].x; ne++) {
            int u = edges[ne].u, v = edges[ne].v, fu = find(u), fv = find(v);
            if(fu == fv) continue;
            if(siz[fu] > siz[fv]) {
                std::swap(u, v); std::swap(fu, fv);
            }
            rt[fv] = merge(rt[fu], rt[fv]);
            fa[fu] = fv; siz[fv] += siz[fu];
        }
        int fv = find(qur[i].v);
        if(tr[rt[fv]].val < qur[i].k) ans[qur[i].id] = -1;
        else ans[qur[i].id] = tmp[query(rt[fv], 1, n, qur[i].k)];
    }
    for(int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}