【学习笔记&题解】线段树合并瞎吹

大概就是合并俩线段树?重复的点一块儿用,否则直接拉过来指针。大多数都是动态开点写法(比较优美)。

以合并值域线段树为例说明。其复杂度是均摊的,即考虑每一次合并操作的复杂度实际上是两颗线段树重叠的点的数量。因为最后一共有 $n\log |V|$ 个点,所以复杂度是 $O(n\log |V|)$,其中 $V$ 是每个被合并元素的值域。

值得注意的是有些题同样需要维护合并之前的信息,那么合并的时候就需要新建节点当根。但根据主席树那套理论,本质上空间复杂度只会多个 $\log$ ?(存疑

$1$ [USACO17JAN]Promotion Counting

给定一棵树,对于所有的 $i\in[1,n]∩\mathbb{Z}$ ,求以 $i$ 为根的子树内有多少权值 $>i$ 的点。

大概是比较裸的线段树合并了?

考虑如果按照正常地线段树合并方式,从底向上合并,那么离散化后对于每个点只需要查询线段树内 $base_i\sim n$ 的数字个数和。于是就完了。

有两个点需要注意:

  • 1、线段树合并不同于普通的值域线段树建立,每次 update 可能会存在走重复节点的情况(否则复杂度就不对了)。所以需要特判 if (!Rt) Rt = ++ Id ;
  • 2、本题由于保证了 $base_i$ 互异,所以离散化可以用一种比较有趣的方式进行:
1
2
3
4
5
6
7
8
bool comp(int a, int b){
return base[a] < base[b] ;
}
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), t[i] = i ;
sort(t + 1, t + n + 1, comp), base[t[1]] = 1 ;
for (int i = 2 ; i <= n ; ++ i)
scanf("%d", &f), add(f, i), base[t[i]] = i ;

其实也是很简单的吧?类似的 $trick$ 以前用过好多次了?

然后以下是总代码。大概就背一背 merge 就好了(

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
const int N = 200010 ;
struct Edge{
int to, next ;
}E[N] ; int head[N], cnt ;
int lc[N * 15], rc[N * 15] ;
int rt[N * 15], val[N * 15] ;
int n, m, ans[N], base[N], t[N], Id ;

bool comp(int a, int b){
return base[a] < base[b] ;
}
void add(int u, int v){
to(++ cnt) = v,
next(cnt) = head[u], head[u] = cnt ;
}
void update(int &Rt, int l, int r, int v){
if (!Rt) Rt = ++ Id ; val[Rt] ++ ;
if (l == r) return ; int mid = (l + r) >> 1 ;
if (v <= mid) update(lc[Rt], l, mid, v) ;
else update(rc[Rt], mid + 1, r, v) ;
}
int merge(int x, int y){
int now = ++ Id ;
if (!(1ll * x * y)) return x + y ;
val[now] = val[x] + val[y] ;
lc[now] = merge(lc[x], lc[y]),
rc[now] = merge(rc[x], rc[y]) ;
return now ;
}
int query(int root, int l, int r, int ql, int qr){
int mid = (l + r) >> 1, res = 0 ;
if (l >= ql && r <= qr) return val[root] ;
if (ql <= mid) res += query(lc[root], l, mid, ql, qr) ;
if (qr > mid) res += query(rc[root], mid + 1, r, ql, qr) ;
return res ;
}
void dfs(int u){
for (int k = head[u] ; k ; k = next(k))
dfs(to(k)), rt[u] = merge(rt[u], rt[to(k)]) ;
ans[u] = query(rt[u], 1, n, base[u] + 1, n), update(rt[u], 1, n, base[u]) ;
}
int main(){
cin >> n ; int f ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), t[i] = i ;
sort(t + 1, t + n + 1, comp), base[t[1]] = 1 ;
for (int i = 2 ; i <= n ; ++ i)
scanf("%d", &f), add(f, i), base[t[i]] = i ;
dfs(1) ;
for (int i = 1 ; i <= n ; ++ i)
printf("%d\n", ans[i]) ; return 0 ;
}

$2$ [POI2011]ROT-Tree Rotations

给出一棵 $n(1≤n≤200000)$ 个叶子的二叉树,可以交换每个点的左右子树,要求前序遍历叶子的逆序对最少。

很妙的一道线段树合并题。

首先,考虑由于只能交换左右子树,所以对于一个点,后代的子树怎么变对其答案没有影响。发现用线段树合并来维护特别合适:对于每个点是否交换左右子树,分别算出新增的逆序对个数然后取 $\min$,该过程可以在 merge 中直接进行——维护值域的 $\rm exist_sum$ 之后,每次只需要用乘法原理求一下即可。

然后就是这题读入很诡…

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
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

#define il inline
typedef long long LL ;

const int N = 200011 ;
const int M = 400011 ;
const int NN = 6000011 ;

int n, cnt ;
int lc[NN], rc[NN], rt[NN] ;
LL ans, val[NN], ans1, ans2 ;

const int ch_top = 5e7 + 1 ;
char ch[ch_top], *now_r = ch - 1, *now_w = ch - 1 ;

il int read(){
while (*++now_r < 48) ;
register int x = *now_r - 48 ;
while (*++now_r >= 48) x = (x << 1) + (x << 3) + *now_r - 48 ;
return x ;
}
il void write(LL x){
static char st[20] ; static int top ;
while (st[++ top] = 48 + x % 10, x /= 10) ;
while (*++ now_w = st[top], -- top) ; *++ now_w = ' ' ;
}
void update(int &Rt, int l, int r, int v){
if (!Rt)
Rt = ++ cnt ;
val[Rt] ++ ;
if (l == r) return ;
int mid = (l + r) >> 1 ;
if (v <= mid) update(lc[Rt], l, mid, v) ;
else update(rc[Rt], mid + 1, r, v) ;
}
int merge(const int &x, const int &y){
if (!x || !y)
return x + y ;
val[x] += val[y] ;
ans1 += val[lc[x]] * val[rc[y]] ;
ans2 += val[rc[x]] * val[lc[y]] ;
lc[x] = merge(lc[x], lc[y]) ;
rc[x] = merge(rc[x], rc[y]) ;
return x ;
}
void dfs(int &x){
int y, ls, rs ;
y = read() ;
if (!y){
ls = rs = 0 ;
dfs(ls), dfs(rs) ; ans1 = ans2 = 0 ;
x = merge(ls, rs) ; ans += min(ans1, ans2) ;
}
else update(x, 1, n, y) ;
}
int main(){
fread(ch, 1, ch_top, stdin) ;
n = read() ; int u = 0 ; dfs(u) ; write(ans) ;
fwrite(ch, 1, now_w - ch, stdout) ; return 0 ;
}

$3$ [Vani有约会]雨天的尾巴

给出一棵 $n$ 个结点的树。共 $m$ 次操作,每次给出树上的一条路径,给路径上所有点添加一个权值为 $w$ 的元素。最后输出每个点出现次数最多的元素的权值。

考虑暴力去剖,发现这么做是 $\frac{n^2\log^2 n}{\omega}$的,即暴力合并 bitset.

但是发现可以离线,于是考虑直接用剖去维护树上差分。那么考虑,对于最终的 $m$ 组询问,可以处理为 $n\log n$ 段 $dfn$ 上的序列差分。

于是对这些差分再用权值线段树从头开始扫一遍就完了。最终复杂度 $O(n\log n)\times O(\log n)=O(n\log^2n)$ 。

但其实发现,树上差分然后拆区间这个过程完全可以用dfs+线段树合并来替代,于是复杂度降为 $n\log n$ 。

…但其实第二个做法其中拆询问的那个 $\log$ 跟本跑不满,再加上线段树合并的复杂度,均摊出来是在是有点 $gg$,于是似乎链剖踩爆了线段树合并的亚子QAQs。

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
void dfs(int u, int f){
dep[u] = dep[f] + 1 ;
fa[u] = f, sz[u] = 1 ;
for (int k = head[u] ; k ; k = next(k)){
if (to(k) == f) continue ;
dfs(to(k), u), sz[u] += sz[to(k)] ;
if (!son[u] || sz[son[u]] < sz[to(k)]) son[u] = to(k) ;
}
}
void dfs(int u, int f, int tp){
top[u] = tp ;
if (son[u]) dfs(son[u], u, tp) ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != son[u] && to(k) != f) dfs(to(k), u, to(k)) ;
}
int lca(int u, int v){
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v) ;
u = fa[top[u]] ;
}
return dep[u] > dep[v] ? v : u ;
}
il void _up(const int &u){
if (s[lc[u]] > s[rc[u]])
s[u] = s[lc[u]], val[u] = val[lc[u]] ;
else if (s[lc[u]] < s[rc[u]])
s[u] = s[rc[u]], val[u] = val[rc[u]] ;
else s[u] = s[lc[u]], val[u] = min(val[lc[u]], val[rc[u]]) ;
}
void update(int &u, int l, int r, int p, int v){
if (!u) u = ++ cnt ;
if (l == r) {
s[u] += v ;
val[u] = s[u] ? r : 0 ;
return ;
}
int mid = (l + r) >> 1 ;
if (p <= mid) update(lc[u], l, mid, p, v) ;
else update(rc[u], mid + 1, r, p, v) ; _up(u) ;
}
int merge(int x, int y, int l, int r){
if (!x || !y) return x + y ;
if (l == r)
return s[x] += s[y], val[x] = l, x ;
int mid = (l + r) >> 1 ;
lc[x] = merge(lc[x], lc[y], l, mid) ;
rc[x] = merge(rc[x], rc[y], mid + 1, r) ;
_up(x) ; return x ;
}
void do_do(int x, int f){
for (int k = head[x] ; k ; k = next(k))
if (to(k) != f)
do_do(to(k), x),
rt[x] = merge(rt[x], rt[to(k)], 1, S) ;
ans[x] = val[rt[x]] ;
}
int main(){
cin >> n >> m ;
int u, v, z, f ;
for (int i = 1 ; i < n ; ++ i)
scanf("%d%d", &u, &v), add(u, v) ;
dfs(1, 0) ; dfs(1, 0, 1) ; cnt = 0 ;
for (int i = 1 ; i <= m ; ++ i){
qr(u), qr(v),
qr(z), f = lca(u, v) ;
update(rt[u], 1, S, z, 1) ;
update(rt[v], 1, S, z, 1) ;
update(rt[f], 1, S, z, -1) ;
if (fa[f]) update(rt[fa[f]], 1, S, z, -1) ;
}
do_do(1, 0) ;
for (int i = 1 ; i <= n ; ++ i)
printf("%d\n", ans[i]) ; return 0 ;
}

$4 $ [HNOI2012] 永无乡

你需要维护若干连通快,有两个操作:

  • 合并 $x,y$ 所在的连通块。
  • 询问 $x$ 所在连通块中权值从小到大排第 $k$ 的结点编号。

$1\leq n,q\leq 3\cdot 10^5$

fa♂现线段树合并之后直接在线段树上二分就做完了,$n\log n$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1 ; i <= q ; ++ i){
scanf("%s", I + 1) ;
if (I[1] == 'B'){
u = qr(), v = qr() ;
int f1 = find(u), f2 = find(v) ;
if (f1 != f2) fa[f2] = f1, rt[f1] = merge(rt[f1], rt[f2]) ;
}
else {
u = qr(), k = qr(), u = find(u) ;
if (s[rt[u]] < k) printf("-1\n") ;
else printf("%d\n", query(rt[u], 1, n, k)) ;
}
}