原题链接： 洛谷P4197 Peaks
肖然大佬的视频教程

题目描述

给出一个 $n$ 个点 $m$ 条边的有点权有边权的无向图，有 $q$ 个询问，
每次询问求从点 $v$ 出发只经过边权小于等于 $x$ 的边，能抵达的第 $k$ 大的点的点权

$n \leq 10^5$
$m, q \leq 5 × 10^5$
$点权，边权 \leq 10^9$

输入样例

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

输出样例

6
1
-1
8

离线线段树合并

首先把点权离散化，在每个点上建一棵线段树，维护点权区间的 $size$

然后把边按照边权排序，把询问按照边权 $x$ 排序

由于询问是递增的，我们就可以把边权小于等于 $x$ 的每一条边所连接的点合并
并查集合并连通块，同时合并线段树

对于每个询问我们在合并之后的线段树内二分即可找到第 $k$ 大的点

时间复杂度 $O((n + m)logn)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 100010, M = 500010;

int n, m, k;
int h[N];

vector<int> hs;
int find(int x)
{
    return lower_bound(hs.begin(), hs.end(), x) - hs.begin();
}

struct Edge{
    int a, b, w;
    bool used;
    bool operator< (const struct Edge &W) const {
        return w < W.w;
    }
}e[M];

int p[N];
int fand(int x)
{
    if(x != p[x])  p[x] = fand(p[x]);
    return p[x];
}

struct Query{
    int root, x, k, num;
    bool operator< (const struct Query &W) const {
        return x < W.x;
    }
}q[M];

struct Node{
    int l, r;
    int sz;
}tr[N * 18];

int root[N], tot;

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

int merge(int x, int y, int l, int r)
{
    if(!x or !y)  return x + y;

    int u = x;
    tr[u].sz = tr[x].sz + tr[y].sz;
    if(l == r)  return u;
    int mid = l + r >> 1;
    if(tr[x].l or tr[y].l)  tr[u].l = merge(tr[x].l, tr[y].l, l, mid);
    if(tr[x].r or tr[y].r)  tr[u].r = merge(tr[x].r, tr[y].r, mid + 1, r);
    return u;
}

int query(int u, int l, int r, int k)
{
    if(tr[u].sz < k)  return -1;
    if(l == r)  return hs[l];

    int mid = l + r >> 1;
    if(tr[tr[u].r].sz >= k)  return query(tr[u].r, mid + 1, r, k);
    return query(tr[u].l, l, mid, k - tr[tr[u].r].sz);
}

int res[M];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]),  hs.push_back(h[i]), p[i] = i;
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());

    for(int i = 0; i < m; i ++)  scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].w);
    sort(e, e + m);

    for(int i = 0; i < k; i ++)
    {
        scanf("%d%d%d", &q[i].root, &q[i].x, &q[i].k);
        q[i].num = i;
    }
    sort(q, q + k);

    for(int i = 1; i <= n; i ++)  insert(root[i], 0, hs.size() - 1, find(h[i]));

    for(int i = 0, j = 0; i < k; i ++)
    {
        while(j < m and e[j].w <= q[i].x)
        {
            int a = e[j].a, b = e[j].b;
            int pa = fand(a), pb = fand(b);
            if(pa != pb)
            {
                root[pb] = merge(root[pa], root[pb], 0, hs.size() - 1);
                p[pa] = pb;
            }
            j ++;
        }
        res[q[i].num] = query(root[fand(q[i].root)], 0, hs.size() - 1, q[i].k);
    }

    for(int i = 0; i < k; i ++)  printf("%d\n", res[i]);
    return 0;
}