【学习笔记】兔队线段树

其实真正的题目应该是「小粉兔教你如何玩转线段树」。这件事要回溯到去年 CSP 之前，有人在 uoj 群里问了一道题的做法：[Luogu U96354](https://www.luogu.com.cn/problem/U96354) 。然后兔队飞快的 A 了这道题并在 uoj 群给出了代码链接。当时就带着机房小伙伴学习了一波…233 然后今天又看到了兔的博文：[从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法](https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html)。 感觉很神仙，然后就打算把这三道题都整理一下。 ~~所以就是类似于复刻了一下兔秒掉or推荐的题~~。 分别是三道题：`LGU96354 魔能阵列`，`BZOJ2957 楼房重建` 和 `CF671E Organizing a Race` . # LGU96354 魔能阵列 > 给定两个序列 $\{a_n\},\{b_n\}$，定义一段区间 $[l,r]$ 的权值为 $$ \sum_{i=l}^r[b_i>0]a_i $$ > 现在给定两种操作，对 $\{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 ```cpp 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$ 。 ```cpp 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$，因为比较毒瘤。大概最后就是转化成了令 $$t_i=suf_i-\min_{j=1}^i\{suf'_j\}$$ 求最大的 $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'$ 。 这里就先只给出线段树部分的代码： ```cpp 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)) ; } } ```