洛谷P3224 [HNOI2012]永无乡

十一月 05, 2020 3872

题意简述

维护一个带点权的动态图，要求支持加一条边，查询某个连通块中点权第 k 小的点编号。

点数量、点权 \leq 10^5 ，操作数 \leq 3\times 10^5

解题思路

看到查询第 k 小，很容易想到二叉搜索树、权值线段树、权值树状数组等数据结构。

那么一个很显然的想法就是，我们对每个连通块维护一个权值数据结构，用于查询第 k 大，在两个连通块之间加边就是合并两个数据结构。

树状数组好像除了 hash 没什么好的合并方法，平衡树难写难调而且我也不会，所以我们就可以愉快地采用动态开点权值线段树来实现查询第 k 大和线段树合并啦！

下面是线段树合并简介。

其实非常好写，就是一句话：人有我有节点合并，人有我无节点继承，人无我有节点不管，递归处理左右儿子。

感觉有点可持久化那味。看代码：

1
2
3
4
5
6
7
8
9
10
11
// 将以 p2 为根的线段树合并进以 p1 为根的线段树
void Merge(int &p1, int p2) {
    // 人有我无节点继承
    if (!p1) { p1 = p2; return; } 
    // 人无我有节点不管
    if (!p2) return;
    // 人有我有节点合并
    sum[p1] += sum[p2];
    // 递归处理左右儿子
    Merge(ls[p1], ls[p2]); Merge(rs[p1], rs[p2]);
}

代码实现

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
// 原题 P3224 [HNOI2012]永无乡
// 题目大意：动态图，支持加一条边，查询某连通块点权第 k 小

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

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 
#define ALL(x) (x).begin(), (x).end()

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    // int s = 0, x = 1; char ch = getchar();
    // while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    // while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    // return s * x;
    int x; scanf("%d", &x); return x;
}

const int MAXN = 100000 + 10;

int n, m, q;
int ref[MAXN];

struct DSU {
    int u[MAXN];
    
    int Find(int x) { return !u[x] ? x : u[x] = Find(u[x]); }
} dsu;

namespace SegtTree {
    static const int SIZ = 2000000 + 10;

    int sum[SIZ];
    int root[MAXN], cnt, ls[SIZ], rs[SIZ];

    void Update(int p) { sum[p] = sum[ls[p]] + sum[rs[p]]; }
    void Insert(int &p, int l, int r, int pos) {
        if (!p) p = ++cnt;
        if (l == r) { ++sum[p]; return; }
        int mid = (l + r) >> 1;
        if (pos <= mid) Insert(ls[p], l, mid, pos);
        else Insert(rs[p], mid + 1, r, pos);
        Update(p);
    }
    void Merge(int &p1, int p2) {
        if (!p1) { p1 = p2; return; } 
        if (!p2) return;
        sum[p1] += sum[p2];
        Merge(ls[p1], ls[p2]); Merge(rs[p1], rs[p2]);
    }
    int Query(int p, int l, int r, int rank) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (sum[ls[p]] >= rank) return Query(ls[p], l, mid, rank);
        else return Query(rs[p], mid + 1, r, rank - sum[ls[p]]);
    }
}

int main() {
    n = read(); m = read();
    using SegtTree::root;
    for (int i = 1; i <= n; ++i) {
        int x = read(); ref[x] = i;
        SegtTree::Insert(root[i], 1, n, x);
    }
    // for (int i = 1; i <= n * 4; ++i) printf("%d%c", SegtTree::sum[i], " \n"[i == 4 * n]);
    for (int i = 1; i <= m; ++i) {
        int u = dsu.Find(read()); int v = dsu.Find(read());
        dsu.u[u] = v;
        SegtTree::Merge(root[v], root[u]);
    }
    q = read();
    for (int i = 1; i <= q; ++i) {
        char op[2]; scanf("%s", op);
        int x = read(); int y = read();
        if (op[0] == 'Q') {
            x = dsu.Find(x);
            if (SegtTree::sum[root[x]] < y) puts("-1");
            else printf("%d\n", ref[SegtTree::Query(root[x], 1, n, y)]);
        } else {
            x = dsu.Find(x); y = dsu.Find(y);
            if (x == y) continue;
            dsu.u[x] = y;
            SegtTree::Merge(root[y], root[x]);
        }
    }
    return 0;
}