【学习笔记】兔队线段树

其实真正的题目应该是「小粉兔教你如何玩转线段树」。这件事要回溯到去年 CSP 之前,有人在 uoj 群里问了一道题的做法:Luogu U96354 。然后兔队飞快的 A 了这道题并在 uoj 群给出了代码链接。当时就带着机房小伙伴学习了一波…233

然后今天又看到了兔的博文:从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法。 感觉很神仙,然后就打算把这三道题都整理一下。

所以就是类似于复刻了一下兔秒掉or推荐的题

分别是三道题:LGU96354 魔能阵列BZOJ2957 楼房重建CF671E Organizing a Race .

LGU96354 魔能阵列

给定两个序列 $\{a_n\},\{b_n\}$,定义一段区间 $[l,r]$ 的权值为

现在给定两种操作,对 $\{b_n\}$ 区间加 $x$ (可正可负) 和询问某个区间的权值。保证任何时刻 $b_i\geq 0$ 。

$1 \leq n,m\leq 2 \times 10^5$

一个比较自然的想法,是分别维护区间 $b_i=0$ 的和 and 区间 $b_i\not = 0$ 的和。但是这个东西维护起来复杂度并不对。所以考虑换一下,由于保证任意时刻 $b_i\geq 0$ ,所以维护区间最小值, 区间 $b_i$ 的值 = 最小值的权值 and 区间 $b_i$ 的值 $\not =$ 最小值的权值和。那么转移就分类讨论一下即可。回答询问的时候只需要再建立一个虚点,对询问区间进行合并,最后只需要判断该区间最小值是否是 $0$ 即可。

大概首先维护区间最小值是个 trick ,建一个虚点对 $\log n$ 个区间进行合并也是一个 trick 。但是这俩似乎我都不是很熟,导致我当时不太会做.jpg

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
using namespace std ; 
int cnt, _tag[MAXN << 2] ;
int s[MAXN << 2], v[MAXN << 2] ;
int N, M, base[MAXN], mnx[MAXN << 2] ;

il int qr(){
char c = getchar() ; int res = 0, fg = 1 ;
while (!isdigit(c)) { if (c == '-') fg = -1 ; c = getchar() ;}
while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
return res * fg ;
}
il void _merge(int x, int y){
if (mnx[x] == mnx[y])
s[x] = s[x] + s[y], v[x] = v[x] + v[y] ;
else if (mnx[x] < mnx[y]) s[x] = s[x] + s[y] + v[y] ;
else mnx[x] = mnx[y], s[x] = s[x] + s[y] + v[x], v[x] = v[y] ;
}
il void _merge(int rt, int ls, int rs){
if (mnx[ls] == mnx[rs])
mnx[rt] = mnx[ls], s[rt] = s[ls] + s[rs], v[rt] = v[ls] + v[rs] ;
else if (mnx[ls] > mnx[rs])
mnx[rt] = mnx[rs], s[rt] = s[ls] + s[rs] + v[ls], v[rt] = v[rs] ;
else mnx[rt] = mnx[ls], s[rt] = s[ls] + s[rs] + v[rs], v[rt] = v[ls] ;
}
il void pdown(int rt){
if (_tag[rt]){
mnx[rt << 1] += _tag[rt] ;
mnx[rt << 1 | 1] += _tag[rt] ;
_tag[rt << 1] += _tag[rt] ;
_tag[rt << 1 | 1] += _tag[rt] ;
_tag[rt] = 0 ;
}
}
il void init(int rt){
mnx[rt] = Inf, s[rt] = 0, v[rt] = 0 ;
}
void build(int rt, int l, int r){
int mid = (l + r) >> 1 ; ++ cnt ;
if (l == r) return v[rt] = base[l], void() ;
build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r) ;
_merge(rt, rt << 1, rt << 1 | 1) ;
}
void update(int rt, int l, int r, int ul, int ur, int x){
if (l >= ul && r <= ur)
return void(mnx[rt] += x, _tag[rt] += x) ;
int mid = (l + r) >> 1 ; pdown(rt) ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, x) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, x) ;
_merge(rt, rt << 1, rt << 1 | 1) ;
}
void query(int rt, int l, int r, int ql, int qr, int ans){
if (l >= ql && r <= qr)
return _merge(ans, rt), void() ;
pdown(rt) ; int mid = (l + r) >> 1 ;
if (ql <= mid) query(rt << 1, l, mid, ql, qr, ans) ;
if (qr > mid) query(rt << 1 | 1, mid + 1, r, ql, qr, ans) ;
_merge(rt, rt << 1, rt << 1 | 1) ;
}
int main(){
cin >> N >> M ; int i ;
for (i = 1 ; i <= N ; ++ i) base[i] = qr() ;
build(1, 1, N) ; (cnt *= 2) += 1 ; int l, r, x, opt ;
while (M --){
opt = qr() ;
if (opt == 1){
l = qr(), r = qr(), x = qr(), update(1, 1, N, l, r, x) ;
}
else{
++ cnt, l = qr(), r = qr() ;
init(cnt), query(1, 1, N, l, r, cnt) ;
printf("%d\n", mnx[cnt] ? s[cnt] + v[cnt] : s[cnt]) ;
}
}
}

bzoj2957 楼房重建

单点修改,查询整个序列有多个前缀最大值。

$1\leq n,m\leq 10^5$

sto 兔。

首先考虑这东西暴力做的话,就是在模拟一个单调栈的过程。带修的话就要考虑套一个 ds。考虑 ds 的作用,本质上是要在每次修改完 $x$ 之后,将 $[1,x-1]$ 和 $[x+1,n]$ 这两个区间的单调栈和 $x$ 放在一起合并。于是不难想到要用线段树。

但…线段树似乎也没法快速合并。考虑每次 push_up 暴力把右区间合并到左区间里面,这样做显然是单次 $O(n)$ 的。考虑发掘更深一些,每次合并左右区间时,左区间是不受影响的,只需要统计左区间最大值对右区间答案的贡献。考虑每次合并,左区间最大值对右区间的影响一定是一个右区间的一个前缀。所以只需要每次合并时,线段树上二分出这个前缀的位置来即可。

然后实现的时候需要注意,二分完前缀之后,前缀的贡献是 $1$ ,剩下的后缀贡献不是 $cnt_{rc}$ 而是 $cnt_{root}-cnt_{lc}$ 。因为此时需要加上的是合并之后右区间对整体有多少贡献。

这样线段树二分 $1$ 个 $\log $ ,本身 update 又是 $1$ 个 $\log $ 。复杂度 $m\log ^2 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
int n, m ; 
db base[N] ;
db s[N * 3] ;
int cnt[N * 3] ;

void build(int rt, int l, int r){
if (l == r){
s[rt] = 0 ;
cnt[rt] = 1 ; return ;
}
int mid = (l + r) >> 1 ;
build(ls, l, mid) ;
build(rs, mid + 1, r) ;
}
int query(int rt, int l, int r, db v){
if (l == r)
return (s[rt] > v) ;
int mid = (l + r) >> 1 ;
if (s[ls] > v)
return query(ls, l, mid, v) + cnt[rt] - cnt[ls] ;
else return query(rs, mid + 1, r, v) ;
}
void update(int rt, int l, int r, int p){
if (l == r)
return void(s[rt] = base[l]) ;
int mid = (l + r) >> 1 ;
if (mid >= p)
update(ls, l, mid, p) ;
else update(rs, mid + 1, r, p) ;
s[rt] = max(s[ls], s[rs]) ;
cnt[rt] = cnt[ls] + query(rs, mid + 1, r, s[ls]) ;
}
int main(){
cin >> n >> m ;
build(1, 1, n) ; int x ; db y ;
for (int i = 1 ; i <= m ; ++ i){
x = qr(), y = qr(), base[x] = (1.0 * y) / (1.0 * x) ;
update(1, 1, n, x) ; printf("%d\n", query(1, 1, n, 0)) ;
}
}

CF671E Organizing a Race

有 $n$ 个点依次排成一列,第 $i$ 个点与第 $i + 1$ 个点之间的距离为 $w_i$ 个单位。

第 $i$ 个点有一个加油站,可以给你的车加能跑 $g_i$ 个单位的油。

你需要在 $l, r$ 之间往返($l \le r$),也就是说,要满足一辆没有油的车能从 $l$ 一路向右开到 $r$,也能从 $r$ 一路向左开到 $l$。

车会在起点加好油,你可以在中途加油,但是方向是不能改变的。你可以假设车的油箱是无限大的。

你还没选好 $l, r$ 的具体取值,不过你希望让你经过的点数尽量多,也就是让 $r - l + 1$ 尽量大。

你现在有 $k$ 个机会,每个机会可以将任意一个 $g_i$ 增加 $1$。

问:使用 $k$ 次机会后,能得到的最大的 $r - l + 1$ 是多少?

这个地方的转化会单独开一篇新的 $blog$,因为比较毒瘤。大概最后就是转化成了令

求最大的 $i$ 满足 $t_i\leq k$ 。然后要支持 $suf’_i$ 的区间加/减以及多次询问。

考虑后一半就是前缀最小值,因为带上修改比较麻烦,所以维护起来依然要选择楼房重建的方式,拿左区间的最小值去二分右区间的前缀。于是可以比较简单地维护出一个区间的 $\min\{t_i\}$ 。

考虑修改。修改的话就是暴力打标记,注意到 $t_i$ 中的 $suf’$ 是负贡献,被 $\min$ 套着,但由于是区间修改所以可以直接减。

考虑如何查询。询问比较麻烦,因为相当于查询时要合并多个区间的单调栈,所以无法直接线段树二分。或者说,需要魔改一下二分,让这个二分可以「边二分,边合并」。

考虑一种比较神秘的方式去找。query(root, l, r, val) 查询的是区间 $[1,l-1]$ 内某个数 val,作为前缀最小值对区间 $[l,r]$ 有影响时,最靠右的 $\leq m$ 的位置。那么考虑分类:

1、如果当前左孩子区间的 $\min\{suf_j’\}$ 比 $val$ 要小,说明当前的前缀最小值不会对右区间产生影响(因为左右区间已经合并了),那么就可以直接判断在算上左区间对右区间贡献时,右区间 $t$ 的最小值是否 $\leq m$ —— 这就是比较朴素的线段树上二分 —— 如果是的话就应该去右儿子里面找,否则去左儿子里找。

2、如果当前左孩子区间的 $\min\{suf_j’\}$ 比 $val$ 要大,说明左区间对右区间产生的贡献会被 $val$ 产生的贡献代替,所以直接递归进右孩子。并且由于 $val$ 已经变成了当前左区间的前缀最小值,所以左区间的 $\min\{suf_j’\}$ 就变成了无用信息(因为肯定都比 $val$ 大),只需要查询在 $a_i+val\leq m$ 时的最大下标即可,这一部分可以直接线段树二分。

但…这似乎也不是最终的查询。考虑为了让最后的 $\min_{j=1}^i\{suf’_j\}$ 真的变成从 $1$ 开始到 $i$ 结束的最小值, 所以需要动态修改 $val$ 的值。先序遍历线段树即可。当然也可以直接维护一个前缀最小 $suf’$ 。

这里就先只给出线段树部分的代码:

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
ll s[N * 3] ;
ll sa[N * 3] ;
ll sb[N * 3] ;
ll tag[N * 3] ;

void _down(int rt, int l, int r){//bingo
if (tag[rt]){
s[ls] -= tag[rt] ;
s[rs] -= tag[rt] ;
sb[ls] += tag[rt] ;
sb[rs] += tag[rt] ;
tag[ls] += tag[rt] ;
tag[rs] += tag[rt] ;
tag[rt] = 0 ;
}
}
ll solve(int rt ,int l, int r, ll v){//bingo
if (l == r)
return sa[rt] - v ; // 2
int mid = (l + r) >> 1 ; _down(rt, l, r) ;
if (sb[ls] >= v)
return min(solve(rs, mid + 1, r, v), sa[ls] - v) ;
else return min(solve(ls, l, mid, v), s[rt]) ;
}
void build(int rt, int l, int r){
if (l == r){
sa[rt] = ss[l] ;
sb[rt] = ss[l]
return ;
}
int mid = (l + r) >> 1 ;
build(ls, l, mid) ;
build(rs, mid + 1, r) ;
sa[rt] = min(sa[ls], sa[rs]) ;
sb[rt] = min(sb[ls], sb[rs]) ;
s[rt] = solve(rs, mid + 1, r, sb[ls]) ;
}
void update(int rt, int l, int r, int ul, int ur, ll v){//bingo
if (ul <= l && r <= ur){
tag[rt] += v ;
sb[rt] += v ;
s[rt] -= v ; //1
return ;
}
_down(rt, l, r) ;
int mid = (l + r) >> 1 ;
if (ul <= mid)
update(ls, l, mid, ul, ur, v) ;
if (ur > mid)
update(rs, mid + 1, r, ul, ur, v) ;
sb[rt] = min(sb[ls], sb[rs]) ;
s[rt] = solve(rs, mid + 1, r, sb[ls]) ;
}
int ask(int rt, int l, int r, ll v){//bingo
if (l == r) return l ;
int mid = (l + r) >> 1 ;
if (sa[rs] > v)
return ask(ls, l, mid, v) ;
return ask(rs, mid + 1, r, v) ;
}
int query(int rt, int l, int r, ll &v){//bingo
if (l == r){
int ret ;
ret = sa[rt] - v <= m ? l : 0 ;
v = min(v, sb[rt]) ;
return ret ;
}
int mid = (l + r) >> 1 ; _down(rt, l, r) ;
if (sb[ls] < v){
if (s[rt] <= m){
v = sb[ls] ;
return query(rs, mid + 1, r, v) ;
}
else {
int ret ;
ret = query(ls, l, mid, v) ;
v = min(v, sb[rt]) ; return ret ;
}
}
else {
int ret = 0 ;
if (sa[rt] - v <= m)
ret = ask(ls, l, mid, m + v) ;
return max(ret, query(rs, mid + 1, r, v)) ;
}
}