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

# 前言 本文包含的内容有 ： - 李超树 - 历史标记 - $\text{Seg-beats}$ - $\text{Kinetic Tournament tree}$ （未施工） 参考资料 ： - 国家集训队2016论文集 ： 吉如一《区间最值操作与历史最值问题》 - 国家集训队2020论文集 ： 李白天《浅谈函数最值的动态维护》 [云剪贴板 ：代码合集](https://www.luogu.com.cn/paste/2wudu3hy) # 杂项 - $\bf\color{blue}\Delta$ **标记拼接** - [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。 - $\bf\color{blue}\Delta$ **点积** 维护两个序列 $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有约会]雨天的尾巴 /【模板】线段树合并](https://www.luogu.com.cn/problem/P4556) - [P5327 [ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327) - [P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298) - [P6773 [NOI2020] 命运](https://www.luogu.com.cn/problem/P6773) 其实就是空间换时间。 考虑总点数一直在减小，而初始时只有 $O(n\log n)$ 个即可证明复杂度。 将二度点压缩后可以做到 $O(n)$ 空间，但一般不实用。 # 李超线段树 - [P4097 [HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097) **题意** : 要求维护一种数据结构，支持插入线段，查询某个 $x$ 坐标处所有线段取值的 $\max$ 。 考虑使用线段树维护。我们称某个区间的“优势线段”为在 $mid$ 处取值最大的线段。 当某个区间插入一条新线段的时候，应该与原有的线段比较 $mid$ 处的取值，如果更优则该点新线段占领。 然而,这个区间内仍然有一部分位置,使得旧线段更优。 由于两条一次函数最多只有一个交点,我们能够发现,旧线段更优的部分必然**完全**在$mid$的左边或者右边。 那么我们把被击败的线段继续下放即可。 下放的复杂度是 $O(\log n)$ 的，而一条线段会被拆分成对 $O(\log n)$ 个点的直接操作，所以李超树的复杂度是 $O(log^2n)$ 的。实际上常数很小。 如果维护的不是线段集，而是直线集，复杂度是严格 $O(\log n)$ 的。 - [P4069 [SDOI2016]游戏](https://www.luogu.com.cn/problem/P4069) 首先在 LCA 处把路径拆一下，变成一条向上的和一条向下的。 显然，题目中加数的形式可以转化成有关深度的一次函数。 我们把树剖一下，每条重链采用李超树维护即可。 虽然这里的 “$x$坐标” 不是连续的，但仍然是单调的，可以维护。不必动态开点。 对于区间 $\min$ ，先维护子树 $\min$ 。注意李超树并不是 `Leafy` 的，更新信息要算上自身。 除此之外还有各个不在子区间内但能贡献的一次函数的 $\min$ ，这类似于标记永久化。由于单调性，只需要取区间内的左右端点即可。 千万不要把维护**线段**的李超树当做凸包来思考! 虽然复杂度是 $O(n\log^3 n)$ ，但是李超树和树剖的常数都很小，效率还行。 调了很久，友情提供样例 : [Link](https://www.luogu.com.cn/paste/4qn7gjrf) [评测记录](https://www.luogu.com.cn/record/33158868) - [P4655 [CEOI2017]Building Bridges](https://www.luogu.com.cn/problem/P4655) 我们把拆除与不拆除翻转过来，先全部都拆除，再减去不拆除的贡献。 可以得到这样的方程 : $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)$ 的，而且常数比平衡树小，还好写。 [评测记录](https://www.luogu.com.cn/record/33163018) - [CF932F Escape Through Leaf](https://www.luogu.com.cn/problem/CF932F) 设 $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)$ 的。 [评测记录](https://www.luogu.com.cn/record/46063694) # 前缀最值相关 (兔队线段树) - [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198) **题意** : 平面上有 $n$ 条线段 $(i,0),(i,H_i)$。 支持单点修改 $H_i$ ，查询从 $(0,0)$ 能看到多少条本质不同的线段。 先不考虑修改，尝试求出静态问题的答案。 显然，若楼顶被挡住，其他部分不可能被看见，所以我们只需要考虑楼顶。 计算出每个楼顶与 $(0,0)$ 连线的斜率，若某个楼顶的斜率比前面的都要大，则能被看见。 也即 : 斜率**前缀严格最大值的个数**。 考虑线段树维护，把某个区间当成完整的子问题。 $s[u]$ 为区间 $u$ 的前缀最大值个数， $mx[u]$ 为区间最大值。 在合并两个区间的时候，左边的最大值可能会把右边本来能看见的一部分楼房挡住。 设 $c\big([l,r],x\big)$ 表示 $[l,r]$ 区间中 $\geq x$ 的部分的前缀严格最大值的个数。 则合并 $[l,mid],(mid,r]$ 产生的前缀严格最大值的个数为 $s[lc]+c\big((mid,r],mx[lc]\big)$ 考虑如何求出 $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 / 花神游历各国](https://www.luogu.com.cn/problem/P4145) **题意** : 给出一段长度为 $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」市场](https://loj.ac/problem/6029) **题意** : 给出一段长度为$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$ 的情况，方法有很多。 最粗暴的方法就是记录此时两种数分别是什么，以及个数，不过这样不优美。 观察发现此时这两种数的加减变化量是相同的，我们可以在每次除法时判定，若区间内所有数除完之后加减变化量相同，则用加法标记代替。 [提交记录](https://loj.ac/submission/915227) - [Uoj#228. 基础数据结构练习题](http://uoj.ac/problem/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$ ,极差不变。 类似地应用加法标记即可规避。 [提交记录](https://uoj.ac/submission/434428) ------------ - [HDU5306. Gorgeous Sequence](http://acm.hdu.edu.cn/showproblem.php?pid=5306) **题意** : 给出一段长度为$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](https://www.luogu.com.cn/problem/CF1290E) **题意** : 给出一个排列 $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$ 即可。 [提交记录](http://codeforces.com/contest/1290/submission/94884946) ------------ - 同时 $\min,\max$ **题意** : ①区间对某数取 $\min$。②区间对某数取 $\max$。 ③查询区间和。 $\min,\max$ 夹来夹去，容终究还是会变小的，不会变大。 考虑再维护最小值，次小值然后讨论即可。复杂度仍然是 $O((n+m)\log n)$。 ------------ - 总结 上文的几个算法中，我们通过暴力 $\rm dfs$ ，把取 $\min,\max$ 这一操作，转化成了若干对最大值的加法操作。 我们可以对最大值和其他数分别维护两套标记。 ------------ - 维护两套标记的好处 **题意** : 维护一个序列 $A$ ，支持 : ①区间对某数取 $\min$。②区间对某数取 $\max$。 ③区间加。 有另一个序列 $B$ ，如果某次修改中 $A_i$ 有变化，则 $B_i$ 加一。④询问 $B$ 的区间和。 如果是区间加操作，整个区间的 $A_i$ 都会改变，也就是 $B$ 都加一。 对于 $\min,\max$ 操作，转化为若干对最大/小值的加法操作，结合最大/小值个数，对 $B$ 的影响仍然容易算。 注意最大值和最小值可能相同，此时需要特判避免重复贡献。复杂度仍然是 $O(n\log^2n)$。 ------------ - 「二重奏」 **题意** : 维护两个序列 $A,B$ ,资瓷 ①将 $A$ 对 $x$ 区间取 $\min$。②将 $B$ 对 $x$ 区间取 $\min$。 ③将 $A$ 区间加。 ④将 $B$ 区间加。 ⑤询问 $A_i+B_i$ 的区间最大值。 只有一个数组的时候，我们把值划分成最大值和次大值，现在有两个数组，我们可以进行类似的划分。 某个位置 : 同时为 $A,B$ 的最大值 / 只为 $A$ 的最大值 / 只为 $B$ 的最大值 / 其他数。 维护四套标记就好了。$k$ 个数组则需要 $2^k$ 套标记。 # 历史值问题 历史值 ： 在维护序列 $A$ 的同时，在每次操作后，序列 $A$ 会对序列 $B$ 的对应位置产生相应贡献。 - 历史版本和 ： 每次操作后 $B_i\leftarrow B_i+A_i$。 - 历史最大值 ： 每次操作后 $B_i=\max(B_i,A_i)$。 - 「线段树基础题」 **题意** : ①区间加。 ③查询区间最大值。 ④查询区间历史最大值。 我们用标记来解决这类历史值问题。 - 在线段树标记的下推机制中，某个点存有标记，表示**整一棵子树**在标记存在的时间内都未曾更新。 于是，问题的核心就在于分析单个节点上停留的标记的影响。 在非历史值问题中，我们只关注该节点“当下”的标记是什么，所以我们会直接将标记合并起来。 但在历史值问题中，我们不仅要考虑该节点现在的标记合并结果，还要考虑历史上推来的（按时间为序的）每个标记的依次作用。 为了便于理解，我们**不合并**标记，假设每个节点上有一个队列（按照时间先进先出），放着所有曾经推过来的标记。 下推标记时，将该节点上所有的标记推到两个儿子处，并清空队列。 对于每个节点，维护 $x,m$ 分别表示 : 区间最值, 区间历史最值。 每次有一个区间加 $t$ 标记推来时，令 $x\leftarrow x+t$ 然后 $m\leftarrow \max(m,x)$。 这样做的正确性是显然的，但实际上我们不可能真的存下各个标记。 于是，我们寻找一种方法 **概括一个队列的标记对当前节点的影响**。 先思考对一个点打若干次标记的情形。 设推来的加法标记分别为 $t[1...k]$ ，其前缀和为 $S[1...k]$。 则打上第 $i$ 个标记之后， $x$ 的值为 $x+S[i]$。所以，$m$ 的值为 $\max_{i=0}^kx+S[i]=x+\max_{i=0}^kS[i]$ 于是，只需记录 $\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$ 下推的时候,令: ```cpp 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监控](https://www.luogu.com.cn/problem/P4314) **题意** : ①区间加。 ②区间赋值。 ③查询区间最大值。 ④查询区间历史最大值。 原来曾经是黑题，现在因为技巧进一步普及，掉紫了。 若不考虑赋值操作，则转化为上一题。下面考虑赋值操作。 > 在经典线段树题目中，偶尔可以不思考两个标记的互相作用，直接令两个标记互斥。 > 然而，在维护历史版本的线段树问题中，需要完整地考虑每个标记的历史影响，则不能采用这种手段。 现在在我们的标记队列中，存在两种标记。两种标记混杂的情况并不便于处理。 可以发现，若存在一个赋值标记，则之后整个区间都是同一个数，那么加法标记可以等价地转化为赋值标记。 于是，该标记队列等价于一个加法标记队列紧跟着一个赋值标记队列。加法标记队列用前文的方法处置。 对于赋值操作 $c[1...k]$ ，最终产生的历史最大值为 $\max_{i=1}^kc[i]$ ，记录下这个即可。意义为“赋值标记的历史最大值”。 具体操作可见代码。 - [P6242 【模板】线段树 3](https://www.luogu.com.cn/problem/P6242) 使用 $\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$ ，更新标记的总个数容易计算。 $$ \begin{aligned} &\sum\limits_{i=1}^{|q_1|+|q_2|}\big[q_3[i]=upd\big]{S_3}_t[i]\\ =&\sum\limits_{i=1}^{|q_1|}\big[q_1[i]=upd\big]{S_1}_t[i]+\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]{S_2}_t[i]+{S_1}_t[|q_1|]\\ =&{S_1}_t[|q_1|]\Big(\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]\Big)+\sum\limits_{i=1}^{|q_1|}\big[q_1[i]=upd\big]{S_1}_t[i]+\sum\limits_{i=1}^{|q_2|}\big[q_2[i]=upd\big]{S_2}_t[i]\\ \end{aligned} $$ 于是，再记录 $S_t[|q|]$ 即合并后的加法标记，则可以合并。 具体地，设 $t$ 为加法标记，$mt$ 为加法标记的历史版本和，$upd$ 为更新标记个数。 当 $u\rightarrow v$ 更新时。 ```cpp 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]序列](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p3246-hnoi2016-xu-lie) - [[DS记录]CF997E Good Subsegments](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-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$ 。 $\sum l$ 和 $\sum r$ 比较显然。前者相对下标不变，可以在双指针移动时处理。后者则每移动一次 $r$ 触发 $+1$。 $\sum \min$ 和 $\sum \max$ 是类似的，只讨论后者。 维护单调栈，栈中两个元素之间的左端点对应的 $\max$ 是相同的，贡献可以看做区间加。 而单调栈的变化次数时均摊 $O(n)$ 的，则会产生 $O(n)$ 个区间加法。 将右端点移动到 $r$ 时维护左端点的线段树状态称为版本 $r$。 设 $v(l,r)$ 为区间 $[l,r]$ 的价值。 若我们需要求出 $\sum\limits_{i=l}^rv(i,r)$ ,则在版本 $r$ 做区间求和即可。 我们要求是 $\sum\limits_{i=l}^r\sum\limits_{j=l}^rv(i,j)$ 则要在 $l...r$ 版本同时做区间求和，不难转化成历史版本和问题。 将线段树可持久化可以支持强制在线。 - [Uoj#164. 【清华集训2015】V](http://uoj.ac/problem/164) **题意** : ①区间减 $x$ 并对 $0$ 取 $\max$。 ②区间加。 ③区间赋值。 ④单点查询。 ⑤单点查询历史最大值。 可以设计出一种标记 $(add,y)$ ,表示先加 $add$ 再对 $y$ 取 $\max$. 不难发现题目中的所有操作都可以用这个标记描述 : ①$(-x,0)$，②$(x,-\inf)$，③$(-\inf,x)$。 标记合并的时候,原有 $(a,b)$ 与 $(a_2,b_2)$ 合并,则变为 $(a+a_2,\max(b+a_2,b_2))$。 现在考虑历史最大值如何维护。由于是单点查询，只需把标记推到叶子，我们只需要对标记做手脚。 历史最大值实际上就是标记前缀和的 $\max$。只要能求 $\max$ ，和前面的题目维护方法是相同的。 **按照值域**考虑每个数接受标记之后会变成什么,发现是一个如下图所示的折线: (讲到这里,人人都要画一样的图,我就剻了个图来, $\text{stO灵梦}$)  两个标记的 $\max$ 就是这两个函数的 $\max$ 。不难发现 $\max\big((a,b),(c,d)\big)=\big(\max(a,c),\max(b,d)\big)$。 让最终的标记对叶节点的数作用一次,则得到答案。 [提交记录](https://uoj.ac/submission/434608) ------------ - [Uoj#515. 【UR #19】前进四](http://uoj.ac/problem/515) **题意** : 单点修改，询问 $a_x,⋯,a_n$ 的不同的后缀最小值个数。允许离线。 可以直接沿用「楼房重建」的做法，然而复杂度 $O(n\log^2n)$ 太差，无法获得满分。 注意到每次询问的都是后缀，而且可以离线，考虑如何利用这两条性质。 有如下暴力 : 从末尾向前扫，求出后缀最大值，若其改变则答案$+1$。 可以按数组下标从后向前扫，以时间为下标，设枚举到第 $k$ 个位置， $t_{k}[i]$ 表示当前位置在第 $i$ 个时刻的后缀最大值。 我们发现，某个修改操作的影响，是给某个时间区间 (该次修改生效的区间) 取 $\min$。 查询相当于问某个位置被更改过多少次，不难使用数域划分后的历史版本和标记维护。 具体实现中，对于一个针对最大值的标记，需要记录标记本身被修改的次数。 非常卡常，这可能是差评数量多的原因吧……具体技巧见代码。 [提交记录](https://uoj.ac/submission/434589) ------------ - [Uoj#169. 【UR #11】元旦老人与数列](http://uoj.ac/problem/169) **题意** : ①区间加。 ②区间取$\max$。③查询区间最小值。 ④查询区间历史最小值。 此时若沿用标记 $(add,y)$，则合并时要对标记取 $\min$ ,就发生了下面的事:  可以看到我们并没有让信息量减少。 考虑转而使用容均摊数域划分，变为若干个给最大值的加法操作，就易于维护了。 [提交记录](https://uoj.ac/submission/434592)