[HNOI2012]永无乡|权值线段树合并

神奇的线段树合并

P3224 [HNOI2012]永无乡

题目描述

永无乡包含 n 座岛,编号从 1 到 n ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以 到达岛 b ,则称岛 a 和岛 b 是连通的。

现在有两种操作:

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座,请你输出那个岛的编号。

输入输出格式

输入格式:

第一行是用空格隔开的两个正整数 n 和 m ,分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 n 个数,依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 $a_i$ 和 $b_i$ ,表示一开始就存在一座连接岛 $a_i$和岛 $b_i$的桥。

后面剩下的部分描述操作,该部分的第一行是一个正整数 q ,表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的 格式如上所述,以大写字母 Q 或 B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。

输出格式:

对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表示所询问岛屿的编号。如果该岛屿不存在,则输出 −1 。

输入输出样例

输入样例#1:

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

输出样例#1:

1
2
3
4
5
-1
2
5
1
2

说明

对于 20% 的数据 $n≤1000,q≤1000$

对于 100% 的数据 $n≤100000,m≤n,q≤300000$


观察题目,就是给你一些有权值的点,然后需要一个合并操作和区间查询第k大。区间查询第k大?主席树?哦没有修改操作啊……那普通权值线段树做就好了,虽然空间不足,但是可以动态开点。

动态开点部分可参照NOIP2017D2T3列队一文,这里不再赘述,下面要介绍的是……

权值线段树:正常线段树大家都知道,就是以每个数在数组中的下标为基础建立的线段树,最低层的叶子节点们就是原序列。权值线段树与普通线段树结构类似,但不同的是线段树中不再存数组下标,而是存储一个具体的权值,因而得名。具体来说,权值线段树的叶子节点从左到右依次表示1,2,3,4,5……x出现的次数。这样每个节点所表示的就是在当前区间内出现了多少个数。显然根节点为n。

那么这个东西可以干啥呢?

区间第k小/大

具体流程是:假设现在有一段区间[l,r],我要查询这之中的第k大值。那么我从线段树的根节点向下查询他的左儿子和右儿子。左儿子中一共出现了x个数,如果k>x,那么显然第k大不在左儿子中,那么问题就变成了在右儿子中找第k-x大。如果k<=x,那么第k大就在左儿子中,问题变为在左儿子中找第k大。显然,这样的复杂度是$O(log ~n)$的。

那么现在我们貌似解决了查询问题。但是合并操作呢?

这里还有一种神奇操作:线段树合并

首先使用线段树合并的线段树应该都是动态开点线段树,否则时间复杂度会退化为$O(n)$

初始时我们对每一个独立的点建一个线段树,并维护一个值域cnt。

用并查集维护每个点是否在一个线段树中,需要合并时,若其中一个是空树,则返回另一个;否则,递归将其中一个的左、右子树分别合并到另一个的左、右子树上,并在回溯时更新权值。注意每次合并时要从根节点开始合并。

1
2
3
4
5
6
7
8
int Merge(int x, int y) {
if (!x) return y;
if (!y) return x;
t[y].l = Merge(t[x].l, t[y].l);
t[y].r = Merge(t[x].r, t[y].r);
PushUp(y);
return y;
}

可以看出,所谓的线段树合并并不是通常意义下的把两个树拼接在一起,而是对于相同位置,整合两棵树的信息,合并在一起。因为是相同位置合并,所以这样合并并不会破坏权值线段树的性质。

可以证明,这样合并的均摊时间复杂度是$O(log~n)$。不过我不会证就是了

(还有一种合并方法是每次新建一个节点整合信息,不知道有没有什么不同)

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
#include <cstring>
#include <cstdlib>
#include <cfloat>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#define ls (u << 1)
#define rs (u << 1 | 1)
#define lc (t[u].l)
#define rc (t[u].r)
using namespace std;

const int MAXN = 100010;
int n, m, q, rank[MAXN];
int fa[MAXN], root[MAXN], id[MAXN], cnt;

struct Tree {
int l, r, seg;
}t[MAXN << 2];

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

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

void PushUp(int u) { t[u].seg = t[lc].seg + t[rc].seg; }

void Insert(int &u, int l, int r, int x) {
if (!u) u = ++ cnt;
if (l == r) { t[u].seg ++; return ; }
int mid = (l + r) >> 1;
if (x <= mid) Insert(lc, l, mid, x);
else Insert(rc, mid + 1, r, x);
PushUp(u);
}

int Merge(int x, int y) {
if (!x) return y;
if (!y) return x;
t[y].l = Merge(t[x].l, t[y].l);
t[y].r = Merge(t[x].r, t[y].r);
PushUp(y);
return y;
}

int Query(int u, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (t[lc].seg >= k) return Query(lc, l, mid, k);
else return Query(rc, mid + 1, r, k - t[lc].seg);
}

int main( ) {
char opt[5]; int a, b, r1, r2;
read(n), read(m);
for (int i = 1; i <= n; ++ i) {
read(rank[i]);
id[rank[i]] = i;
root[i] = ++ cnt;
Insert(root[i], 1, n, rank[i]);
}
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= m; ++ i) {
read(a), read(b);
r1 = find(a), r2 = find(b);
Merge(root[r1], root[r2]);
fa[r1] = r2;
}
read(q);
for (int i = 1; i <= q; ++ i) {
scanf("%s", opt); read(a), read(b);
if (opt[0] == 'Q') {
r1 = find(a);
if (t[root[r1]].seg < b) printf("-1\n");
else printf("%d\n", id[Query(root[r1], 1, n, b)]);
}
else {
r1 = find(a), r2 = find(b);
Merge(root[r1], root[r2]);
fa[r1] = r2;
}
}
return 0;
}

不过虽然理论上线段树合并的均摊时间复杂度是$O(n~log~n)$,但是常数巨大,会跑的比$O(n~log^2~n)$的平衡树+启发式合并慢不少。慎用。简单到是真的

{% if theme.fireworks %} {% endif %} {{ live2d() }}