Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P7834 [ONTAK2010] Peaks 加强版

发表于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

P7834 [ONTAK2010] Peaks 加强版

一种显然的离线做法，询问和边按照边权排序，每个连通块用平衡树维护，加边时启发式合并，平衡树需要支持查询第 $k$ 大，这里用 pbds 。一种可以替代平衡树的做法是线段树合并，对于每一个连通块的值维护一棵动态开点值域线段树。

查看代码 
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
#include <cstdio>
#include <algorithm>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
const double eps = 1e-6;
const int N = 5e5 + 10;
int n, m, q, p[N], ans[N];
tree <double, null_type, greater<double>, rb_tree_tag, tree_order_statistics_node_update> g[N];
struct Edge
{
    int u, v, w;
    bool operator < (const Edge &_) const
        { return w < _.w; }
} e[N];
struct Query
{
    int v, x, k, id;
    bool operator < (const Query &_) const
        { return x < _.x; }
} o[N];
int fa (int x) { return p[x] == x ? x : p[x] = fa(p[x]); }
void merge (int a, int b)
{
    a = fa(a), b = fa(b);
    if (a == b) return;
    if (g[a].size() > g[b].size()) swap(a, b);
    p[a] = b;
    for (double i : g[a]) g[b].insert(i);
}
int main ()
{
    read(n, m, q);
    for (int i = 1, a; i <= n; ++i)
        read(a), p[i] = i, g[i].insert(a + i * eps);
    for (int i = 1; i <= m; ++i)
        read(e[i].u, e[i].v, e[i].w);
    for (int i = 1; i <= q; ++i)
        read(o[i].v, o[i].x, o[i].k), o[i].id = i;
    sort(e + 1, e + m + 1);
    sort(o + 1, o + q + 1);
    for (int i = 1, t = 0; i <= q; ++i)
    {
        while (t < m && e[t + 1].w <= o[i].x)
            ++t, merge(e[t].u, e[t].v);
        int x = fa(o[i].v);
        ans[o[i].id] = g[x].size() < o[i].k ? -1 : *g[x].find_by_order(o[i].k - 1);
    }
    for (int i = 1; i <= q; ++i)
        write(ans[i]), puts("");
    return 0;
}

在线的做法。求出 Kruskal 重构树，树上的父子关系和点权是单调的，那么对于每个询问，找到一个点是最高的点权符合条件的点，那么这个点子树的内的所有点是合法的。将其拍成一个序列，那么问题转化为区间最值。可以用主席树。

查看代码 
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
100
101
102
103
#include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
const int N = 2e5 + 10, M = 5e5 + 10, K = 20, D = 5e6 + 10, inf = 1e9;
vector <int> g[N];
int stmp, rnk[N], L[N], R[N];
int n, m, tot, q, h[N], p[N], w[N], f[N][K], v[N][K];
int idx, rt[N];
struct Node { int l, r, c; } tr[D];
void modify (int &x, int t, int l = 1, int r = inf)
{
    tr[++idx] = tr[x];
    ++tr[x = idx].c;
    if (l == r) return;
    int mid = l + r >> 1;
    t <= mid ? modify(tr[x].l, t, l, mid) : modify(tr[x].r, t, mid + 1, r);
}
int query (int x, int y, int k, int l = 1, int r = inf)
{
    if (l == r) return l;
    int mid = l + r >> 1, t = tr[tr[y].l].c - tr[tr[x].l].c;
    return t >= k ? query(tr[x].l, tr[y].l, k, l, mid) : query(tr[x].r, tr[y].r, k - t, mid + 1, r);
}
struct Edge
{
    int u, v, w;
    bool operator < (const Edge &_) const
        { return w < _.w; }
} e[M];
int fa (int x) { return p[x] == x ? x : p[x] = fa(p[x]); }
void dfs (int x)
{
    L[x] = stmp;
    if (g[x].empty()) rnk[++stmp] = x;
    for (int i : g[x])
    {
        f[i][0] = x;
        v[i][0] = w[x];
        for (int k = 0; f[i][k]; ++k)
        {
            f[i][k + 1] = f[f[i][k]][k];
            v[i][k + 1] = max(v[i][k], v[f[i][k]][k]);
        }
        dfs(i);
    }
    R[x] = stmp;
}
int main ()
{
    read(n, m, q);
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int i = 1; i <= n; ++i) read(h[i]);
    for (int i = 1; i <= m; ++i)
        read(e[i].u, e[i].v, e[i].w);
    sort(e + 1, e + m + 1);
    int tot = n;
    for (int i = 1; i <= m; ++i)
    {
        int a = fa(e[i].u), b = fa(e[i].v);
        if (a == b) continue;
        p[a] = p[b] = ++tot; p[tot] = tot;
        g[tot].pb(a), g[tot].pb(b);
        w[tot] = e[i].w;
    }
    for (int i = 1; i <= tot; ++i)
        if (p[i] == i) dfs(i);
    for (int i = 1; i <= n; ++i)
        modify(rt[i] = rt[i - 1], h[rnk[i]]);
    for (int u, x, k, last = 0; q; --q)
    {
        read(u, x, k);
        u = (u ^ last) % n + 1, x ^= last, k = (k ^ last) % n + 1;
        for (int i = K - 1; ~i; --i)
            if (f[u][i] && v[u][i] <= x) u = f[u][i];
        k = R[u] - L[u] - k + 1;
        last = k > 0 ? query(rt[L[u]], rt[R[u]], k) : 0;
        write(last ? last : -1), puts("");
    }
    return 0;
}
相关文章