[luogu4197]Peaks(线段树合并)

Posted on |

Problem

传送门

给你一张$n$个点，$m$条边的图，边有边权，点有点权。

现有$Q$个询问，每次询问从点$x$开始，只走边权小于$y$的边，能走到的点中点权第$k$大的点

Solution

这道题没有强制在线，所以直接想了一个简单的离线做法。

将询问按照y排序，边按照边权排序。

对每个并查集维护一棵权值线段树

将边按顺序一条一条加入，合并了两个并查集的同时合并权值线段树

至于查询，在权值线段树查询全局的k大就可以了。

不知道为什么大家都打的启发式合并+主席树

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
    int res = 0, fl = 1;
    char r = getchar();
    for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
    for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
    return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 5e5 + 10;
namespace SGT{
    int tre[Maxn << 4], ls[Maxn << 4], rs[Maxn << 4], cnt;
#define mid ((l + r) >> 1)
#define sum tre[rs[rt]]
    inline void Insert(int &rt, int l, int r, int pos){
        if(!rt) rt = ++cnt;
        tre[rt]++;
        if(l == r) return;
        if(mid >= pos) Insert(ls[rt], l, mid, pos);
        else Insert(rs[rt], mid + 1, r, pos);
    }
    inline int Query(int rt ,int l, int r, int k){
        if(tre[rt] < 0) return -1;
        if(tre[rt] < k) return -1;
        if(l == r) return l;
        if(sum >= k) return Query(rs[rt], mid + 1, r, k);
        else return Query(ls[rt], l, mid, k - sum);
    }
    inline int merge(int u, int v){
        if(!u) return v;
        if(!v) return u;
        tre[u] += tre[v];
        ls[u] = merge(ls[u], ls[v]);
        rs[u] = merge(rs[u], rs[v]);
        return u;
    }
#undef mid 
#undef sum
}
struct node {
    int x, y, val, id;
    bool operator < (const node T) const{ return val < T.val;}
}g[Maxn],ASK[Maxn];
int ans[Maxn], fa[Maxn], h[Maxn], b[Maxn], root[Maxn], num;
bool vis[Maxn];
vector <int> G[Maxn];
inline int get_fa(int x){ return fa[x] == x ? x : fa[x] = get_fa(fa[x]);}
inline void link(int u, int v){
    if(get_fa(u) == get_fa(v)) return;
    root[get_fa(v)] = SGT::merge(root[get_fa(u)], root[get_fa(v)]);
    fa[get_fa(u)] = get_fa(v);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    int n = read(), m = read(), Q = read();
    for (int i = 1; i <= n; ++i) b[i] = h[i] = read();
    sort(b + 1, b + 1 + n);
    num = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i) h[i] = lower_bound(b + 1, b + 1 + num, h[i]) - b;
    for (int i = 1; i <= m; ++i)
        g[i].x = read(), g[i].y = read(), g[i].val = read();
    sort(g + 1, g + 1 + m);
    for (int i = 1; i <= Q; ++i)
        ASK[i].x = read(), ASK[i].val = read(), ASK[i].y = read(),ASK[i].id = i;
    sort(ASK + 1, ASK + 1 + Q);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i)
        SGT::Insert(root[i], 1, num, h[i]);
    int top = 1;
    for (int i = 1; i <= m; ++i){
        for(; ASK[top].val < g[i].val && top <= Q; ++top){
            ans[ASK[top].id] = SGT::Query(root[get_fa(ASK[top].x)], 1, num, ASK[top].y);
            vis[ASK[top].id] = 1;
        }
        link(g[i].x, g[i].y);
    }
    for (int i = top; i <= Q; ++i)
        ans[ASK[i].id] = SGT::Query(root[get_fa(ASK[i].x)], 1, num, ASK[i].y);
    b[0] = -1;
    for (int i = 1; i <= Q; ++i)
        printf("%d\n",b[max(ans[i], 0)]);
    return 0;
}