关于线段树上的一些进阶操作

command_block · 2020-04-25 17:03:26 · 个人记录

前言

本文包含的内容有 ：

• 李超树

• 历史标记

• \text{Seg-beats}

参考资料 ：

• 国家集训队2016论文集 ： 吉如一《区间最值操作与历史最值问题》

• 国家集训队2020论文集 ： 李白天《浅谈函数最值的动态维护》

云剪贴板 ：代码合集

杂项

• - [SP1716 GSS3 - Can you answer these queries III](https://www.luogu.com.cn/problem/SP1716) - [题解 CF1149C 【Tree Generator™】](https://www.luogu.com.cn/blog/command-block/solution-cf1149c) - [[DS记录]CF1192B Dynamic Diameter](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-cf1192b-dynamic-diameter)

只是 pushup 的技巧，对于所有基于合并的数据结构都适用。

也可以理解为动态DP。

• 维护两个序列 $A,B$ ，支持区间加，查询 $A[i]*B[i]$ 的区间和。

设 s_a,s_b,s_o 分别为 A,B,(A·B) 的区间和。

则给 A 整体加 c 后, s_o\leftarrow s_b*c。

可以扩展到其他的操作，就不再赘述。

线段树合并

• P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

• P5327 [ZJOI2019]语言

• P5298 [PKUWC2018]Minimax

• P6773 [NOI2020] 命运

其实就是空间换时间。

考虑总点数一直在减小，而初始时只有 O(n\log n) 个即可证明复杂度。

将二度点压缩后可以做到 O(n) 空间，但一般不实用。

李超线段树

• P4097 [HEOI2013]Segment

  题意 : 要求维护一种数据结构，支持插入线段，查询某个 x 坐标处所有线段取值的 \max 。

考虑使用线段树维护。我们称某个区间的“优势线段”为在 mid 处取值最大的线段。

当某个区间插入一条新线段的时候，应该与原有的线段比较 mid 处的取值，如果更优则该点新线段占领。

然而,这个区间内仍然有一部分位置,使得旧线段更优。

由于两条一次函数最多只有一个交点,我们能够发现,旧线段更优的部分必然完全在mid的左边或者右边。

那么我们把被击败的线段继续下放即可。

下放的复杂度是 O(\log n) 的，而一条线段会被拆分成对 O(\log n) 个点的直接操作，所以李超树的复杂度是 O(log^2n) 的。实际上常数很小。

如果维护的不是线段集，而是直线集，复杂度是严格 O(\log n) 的。

• P4069 [SDOI2016]游戏

首先在 LCA 处把路径拆一下，变成一条向上的和一条向下的。

显然，题目中加数的形式可以转化成有关深度的一次函数。

我们把树剖一下，每条重链采用李超树维护即可。

虽然这里的 “x坐标” 不是连续的，但仍然是单调的，可以维护。不必动态开点。

对于区间 \min ，先维护子树 \min 。注意李超树并不是 Leafy 的，更新信息要算上自身。

除此之外还有各个不在子区间内但能贡献的一次函数的 \min ，这类似于标记永久化。由于单调性，只需要取区间内的左右端点即可。

千万不要把维护线段的李超树当做凸包来思考!

虽然复杂度是 O(n\log^3 n) ，但是李超树和树剖的常数都很小，效率还行。

调了很久，友情提供样例 : Link

评测记录

• P4655 [CEOI2017]Building Bridges

我们把拆除与不拆除翻转过来，先全部都拆除，再减去不拆除的贡献。

可以得到这样的方程 : F[n]=\min\limits_{i=1}^{n-1} F[i]+(h_n-h_i)^2+W[n]

如果将 h_n 当做变量，可以整理成(h_n^2+W[n])-2h_ih_n+(h_i^2+F[i])

其中，前者是关于目标的常量，可不计，后面则是一个一次函数。

我们发现，这些一次函数的斜率不单增，因此不能仅仅使用单队维护。这里可以使用李超树。

李超树维护直线集合是 O(\log n) 的，而且常数比平衡树小，还好写。

评测记录

• CF932F Escape Through Leaf

设 f[u] 为从 u 点到达叶子的最小花费。

显然有转移 f[u]=\min\limits_{\text{v在u的子树中}}f[v]+a_ub_v。

我们可以把 v 点的转移变成形如 f(x)=b_vx+f[v] 的一次函数，每次代入 a_u 求最小值。

这就可以使用李超树维护了。使用启发式合并，显然有复杂度 O(n\log^2n)。

实际上，直接线段树合并，先合并两棵子树，然后合并根节点信息，由于线段只会被下放，总复杂度是 O(n\log n) 的。

评测记录

前缀最值相关 (兔队线段树)

• P4198 楼房重建

  题意 : 平面上有 n 条线段 (i,0),(i,H_i)。

  支持单点修改 H_i ，查询从 (0,0) 能看到多少条本质不同的线段。

先不考虑修改，尝试求出静态问题的答案。

显然，若楼顶被挡住，其他部分不可能被看见，所以我们只需要考虑楼顶。

计算出每个楼顶与 (0,0) 连线的斜率，若某个楼顶的斜率比前面的都要大，则能被看见。

也即 : 斜率前缀严格最大值的个数。

考虑线段树维护，把某个区间当成完整的子问题。

考虑如何求出 c ，可以直接利用线段树的信息来求解。

若到达叶节点，简单比较大小即可。

若 mx[lc]<x ，左区间的贡献为 0， 此时有 c\big([l,r],x\big)=c\big((mid,r],x\big)。

若 mx[lc]\geq x ，则该点上记录的右侧前缀最大值必然均 >x ，不必再次计算。

此时 c\big([l,r],x\big)=s[u]+c\big([l,mid],x\big)-s[lc]

不难发现上述算法总是只会递归一侧，复杂度是 O(\log n) 的。

总复杂度为 O(n\log^2n)。

兔队指出，上述操作中涉及到了一个减法，若信息不满足可减性，则无法维护。

所以，考虑对各个区间 u=[l,r] 改而维护 : 考虑整个 [l,r] 时 (mid,r] 内的前缀最大值数量。记为 s'[u]。

我们仍然沿用 c\big([l,r],x\big) 的定义，则有 ：

• s[u]=c\big((mid,r],mx[lc]\big)
• mx[lc]<x\Rightarrow c\big([l,r],x\big)=c\big((mid,r],x\big)
• mx[lc]\geq x\Rightarrow c\big([l,r],x\big)=s[u]+c\big([l,mid],x\big)

答案不能直接取用，可以使用 c\big([1,n],0\big) 得到。

Seg-beats

有时候，题目中的操作会使信息量趋向于减小，此时可能产生均摊的做法。

前面的几道均摊小例题并非正统 Seg-beats 内容，较为熟悉的读者可以跳过。

• P4145 上帝造题的七分钟2 / 花神游历各国

题意 : 给出一段长度为 n 的序列，要求支持如下操作:

• 区间开根

• 查询区间和

大小为 S 的正数在开根 O(\log\log S) 次后会变为 1。 0 开根总是 0。

我们在线段树上暴力 dfs ，若发现某个区间内有大于 1 的数才进入。

由于不会在中途停止，到达一次叶节点对应 O(\log n) 的复杂度。

若到达叶节点，必然造成一次开根。总共的开根次数是 O(n\log\log S) 次的。

总复杂度也就是 O(n\log n\log\log S)。

• Loj#6029. 「雅礼集训 2017 Day1」市场

题意 : 给出一段长度为n的序列，要求支持如下操作:

• 区间加

• 区间整除 d

• 询问区间 \min

• 询问区间和

接下来介绍一种典型的势能分析方法 ：容均摊。

即 : 找出一种能概括信息量的“特征值”，证明其消长和时间消耗有关，最终通过求和得到复杂度。

为了行文方便，下文将某节点点包含的信息复杂度称为“容”。

本题中，我们将一个节点的容定义为该节点内数字的极差。

若极差为 0 ，则代表所有的数字都相同，则可以批量操作并打下标记(可以转化成加法标记)。

若极差不为 0 ，则暴力递归下去。

一次除法操作显然可以至少让极差除以 d。对于某个节点，除 O(\log S) 次就能让容变为 0。

任意的整体操作不会影响容的大小。

然而，一次“非整体”的任意修改操作会导致某个节点的容(不可预期地)变化。

一次区间操作最多提供 O(\log n) 次“非整体”的修改操作。

也就是说，每次区间修改操作提供了 O(\log n\log S) 的额外代价。

总复杂度 O(n\log n+m\log n\log S)。

然而，这是不严谨的，如果考虑下取整产生的误差，可能有除法之后极差不变的情况。

如 5,6,5,6 ，在除以 3 之后变为 2,3,2,3 加上 3 之后又变回 5,6,5,6。

这样，每次除法操作都需要暴力，复杂度退化。

我们发现，下取整最多带来 1 的偏差，所以极差为 1 时才有可能除完极差不变。

我们只需要特殊处理极差为 1 的情况，方法有很多。

最粗暴的方法就是记录此时两种数分别是什么，以及个数，不过这样不优美。

观察发现此时这两种数的加减变化量是相同的，我们可以在每次除法时判定，若区间内所有数除完之后加减变化量相同，则用加法标记代替。

提交记录

• Uoj#228. 基础数据结构练习题

题意 : 在 P4145 的基础上，加入区间加操作。

类似地，我们将一个节点的容定义为该节点内数字的极差。

若极差不为 0 ，一次整体开根操作可以至少让极差开根。

证明 : 设原来的极差由 x^2-y^2 产生，而开方后的极差为 x-y ，由 x^2-y^2=(x+y)(x-y) 且 x+y\geq x-y ，不难推知 x-y\leq \sqrt{x^2-y^2}。

需要开根 O(\log\log S) 次才能让容变回 0。每次区间修改操作提供了 O(\log n\log\log S) 的额外代价。

总复杂度 O(n\log n+m\log n\log\log S)。

这同样是不严谨的，下取整仍然可以造成偏差，如 3,4,3,4 开根之后变为 1,2,1,2 ,极差不变。

类似地应用加法标记即可规避。

提交记录

• HDU5306. Gorgeous Sequence

题意 : 给出一段长度为n的序列，要求支持如下操作:

• 区间对某个数取 \min

• 查询区间和

• 查询区间最大值

我们发现所有数值只会变小，即信息量减小。

考虑维护最大值 mx ，最大值的个数 cm ，以及严格次大值 mx2 ，区间和 s .

对于一个修改 y ，如果 y\geq mx ，显然无影响。

如果 mx>y>mx2 ，那么只会对最大值产生影响，利用个数 cm 来计算贡献，并打下标记。

如果 mx2\geq y ，这次操作可能影响到最大值之外的数，我们无法在当前节点处理，只能向深处 dfs ，直到能处理为止。

复杂度看起来玄学，实际上是 O((n+m)\log n) 的。

定义某个点的容为其中数的种类数。所有点的种类数和是 O(n\log n) 的。

如果在 dfs 中需要经过，则至少会将该点最大值和次大值合并使得容减少 1。dfs的额外贡献就是 O(n\log n) 的。

• 加入区间加操作

仍然考虑维护上述四个量 mx,cm,mx2,s。

把标记改进成 (add,y) 的形式，意义为先加上 add 再对 y 取最小值。

取 \min 修改时仍然按照上述规则大力 dfs。

根据论文中的证明，复杂度有上界 O(n\log^2n) ，但实战中的表现近似于 O(n\log n)。

• CF1290E Cartesian Tree

  题意 : 给出一个排列 P ，对于每个 1\leq k\leq n ，询问当保留\leq k 的数时，该序列笛卡尔树(大根堆)的子树大小和。

首先分析一下性质，笛卡尔树的建树可以认为是每次抽取最大值分治。

那么，从 i 出发，设左边第一个大于它的位置为 pre[i] ，右边则为 nxt[i]。

那么， pre[i],nxt[i] 一定比 i 先选取，将 i 与其他区域分隔开了。

现在， i 是区间 (pre[i],nxt[i]) 最大值，那么整个区间一定都在其子树内。

这就证明了 i 的子树大小是 nxt[i]-pre[i]-1。

令 k 从小到大增加，维护 nxt 和 pre 的和即可求出答案。下面只讨论 nxt。

每次会增加一个比先存所有数更大的数，那么其会令左侧的 nxt 对其位置取 \min。

但是注意，还空着的位置是不会计入下标的，我们其实是在 “插入”。

那么,右侧的所有标号都会增加 1 ,即对右侧的 nxt 区间加 1。

区间取 \min ，区间加，维护总和，直接套用上一题的做法即可。

还有一个要注意的是，由于我们在使用线段树，所以不可能真正的插入，而是预留好空位每次填掉。

这样以来，区间操作时，仍为空位的点需要被忽略。

使用维护点积的技巧，将空位的权设为 0 即可。

提交记录

• 同时 \min,\max

题意 : ①区间对某数取 \min。②区间对某数取 \max。 ③查询区间和。

于是，只需记录 \max_{i=0}^kS[i] 就能得知该标记队列对节点的影响。

合并加法标记的方法时简单求和，所以前 i 个标记合并后恰好等于 S[i] ，那么 \max_{i=0}^kS[i] 可以表述为标记的历史最大值。

接下来考虑两个队列如何合并，设为 t_1[1...k_1],t_2[1...k_2] ，合并后的结果为 t_3[1...k_1+k_2]。

注意到 S_3[i]=\begin{cases}S_1[i]&(1\leq i\leq k_1)\\S_1[k_1]+S_2[i-k_1]&(k_1+1\leq i\leq k_1+k_2)\end{cases}

我们需要快速得到 \max_{i=0}^{k_1+k_2}S_3[i]=\max\Big(\max_{i=0}^{k_1}S_1[i],\ S_1[k_1]+\max_{i=0}^{k_2}S_2[i]\Big) 。

维护 S_1[k_1] 即可，这也正是目前加法标记的值。

具体地，设 t 为合并后的加法标记，mt 为加法标记的历史最大值。

每次 u\rightarrow v 下推的时候,令:

v.m=max(v.m,v.x+u.mt);
v.mt=max(v.mt,u.mt+v.t);
v.x+=u.t;
v.t+=u.t;
u.t=u.mt=0;

• P4314 CPU监控

  题意 : ①区间加。 ②区间赋值。 ③查询区间最大值。 ④查询区间历史最大值。

原来曾经是黑题，现在因为技巧进一步普及，掉紫了。

若不考虑赋值操作，则转化为上一题。下面考虑赋值操作。

在经典线段树题目中，偶尔可以不思考两个标记的互相作用，直接令两个标记互斥。

然而，在维护历史版本的线段树问题中，需要完整地考虑每个标记的历史影响，则不能采用这种手段。

现在在我们的标记队列中，存在两种标记。两种标记混杂的情况并不便于处理。

可以发现，若存在一个赋值标记，则之后整个区间都是同一个数，那么加法标记可以等价地转化为赋值标记。

于是，该标记队列等价于一个加法标记队列紧跟着一个赋值标记队列。加法标记队列用前文的方法处置。

对于赋值操作 c[1...k] ，最终产生的历史最大值为 \max_{i=1}^kc[i] ，记录下这个即可。意义为“赋值标记的历史最大值”。

具体操作可见代码。

• P6242 【模板】线段树 3

使用 \rm Seg-beats 维护 A 的区间和。

把区间取 \max 划分成若干对区间最大值的加法操作。

我们维护两套标记，一套只对最大值生效，另一套对所有数都生效。

注意，只对最大值生效的标记下推时要判断儿子是否含有同样的最大值。

历史最大值的合并是要讲究顺序关系的（因为标记队列是有顺序的），所以标记影响的对象必须不交才方便维护。（难以处理多个标记队列）

所以，我们让另一套标记对最大值之外的数（而非所有数）生效。

有若干坑点 :

• 判断儿子是否含有最大值时，要在两个儿子之间比较。

• 若儿子不含有最大值，需要对其（略小的）最大值打上对非最大值生效标记。

具体细节见代码。

• 历史版本和

记原序列为 A ，版本和序列为 B。

可以把 “更新 B 序列”也看作一种标记，每次操作后给整棵树打一个。

考虑一个更新标记和加法标记交替出现的队列，记当前节点区间和为 s ，历史版本和为 ms ，区间长度为 len。

加法标记 t 会令 s\leftarrow s+t*len 。更新标记会使得 ms\leftarrow ms+s。

考虑标记队列 q[1...m]=\{t_1,t_2,upd,t_4,upd...\}

记 S_t[i] 为前 i 个标记中，加法标记的和。

则对 ms 的总贡献为 \sum\limits_{i=1}^{k}\big[q[i]=upd\big]s+S_t[i]*len=s\Big(\sum\limits_{i=1}^{k}\big[q[i]=upd\big]\Big)+len*\sum\limits_{i=1}^{k}\big[q[i]=upd\big]S_t[i]

于是，我们只需记录 \sum\limits_{i=1}^{k}\big[q[i]=upd\big] 和 \sum\limits_{i=1}^{k}\big[q[i]=upd\big]S_t[i] 。

意义是更新标记的总个数，以及每个更新标记打上时，S_t[i] 的和，即加法标记的历史版本和。

若两个队列 q_1,q_2 拼接得到 q_3 ，更新标记的总个数容易计算。

于是，再记录 S_t[|q|] 即合并后的加法标记，则可以合并。

具体地，设 t 为加法标记，mt 为加法标记的历史版本和，upd 为更新标记个数。

当 u\rightarrow v 更新时。

v.ms+= u.upd*v.s + u.mt*v.len;
v.mt+= v.tg*u.upd + u.mt;
v.upd+= u.upd;
v.s+= u.tg*v.len;
v.tg+= u.tg;

• [DS记录]P3246 [HNOI2016]序列

• [DS记录]CF997E Good Subsegments

• \rm Arithmetic

  题意 ： 一个多重集合的价值定义 ： 将其变为公差为 d (给定常数) 的等差数列需要插入几个数字（无法实现则价值为0）。

  多次询问 [l,r] 的子区间的价值和。

若可以变为公差为 d 的等差数列，则称该区间合法。

不难发现，若区间 [l,r] 合法，那么其所有子区间都合法。

我们从每个右端点 l 找到最靠左的 r （这可以双指针求出），所有这些极长区间的子区间的并集就是所有合法的区间。

对于一个合法的区间 [l,r]，其价值容易计算 ： (\max-\min)/d-(r-l)

考虑离线，从左到右移动右端点，并维护每个左端点对应的答案。

当 r 增加时，首先要删掉不合法的部分，这里可以暴力单点删除。

接下来，分别维护 \sum \max ,\sum \min ,\sum l,\sum r 。