Seg Beats - Oi Wiki — ContextQMD

本文讲解吉老师在 2016 年国家集训队论文中提到的线段树处理历史区间最值的问题．

区间最值

笼统地说，区间最值操作指，将区间 $[l,r]$ 的数全部对 $x$ 取 $\max$ 或 $\min$，即 $a_i=\max(a_i,x)$ 或者 $a_i=\min(a_i,x)$．

???+ note "HDU5306 Gorgeous Sequence" 维护一个序列 $a$，执行以下操作：

1.  `0 l r t` $\forall l\le i\le r,~ a_i=\min(a_i,t)$．
2.  `1 l r` 输出 $\max\limits_{i=l}^r a_i$．
3.  `2 l r` 输出 $\sum\limits_{i=l}^r a_i$．

多组测试数据，保证 $T\le 100,~\sum n,\sum m\le 10^6$．

区间取 $\min$，意味着只对那些大于 $t$ 的数有更改．因此这个操作的对象不再是整个区间，而是「这个区间中大于 $t$ 的数」．于是我们可以有这样的思路：每个结点维护该区间的最大值 $Max$、次大值 $Se$、区间和 $Sum$ 以及最大值的个数 $Cnt$．接下来我们考虑区间对 $t$ 取 $\min$ 的操作．

如果 $Max\le t$，显然这个 $t$ 是没有意义的，直接返回；
如果 $Se<t < Max$，那么这个 $t$ 就能更新当前区间中的最大值．于是我们让区间和加上 $Cnt(t-Max)$，然后更新 $Max$ 为 $t$，并打一个标记．
如果 $t\le Se$，那么这时你发现你不知道有多少个数涉及到更新的问题．于是我们的策略就是，暴力递归向下操作．然后上传信息．

这个算法的复杂度如何？使用势能分析法可以得到复杂度是 $O(m\log n)$ 的．具体分析过程见论文．

cpp

--8<-- "docs/ds/code/seg-beats/seg-beats_1.cpp"

???+ note "BZOJ4695 最假女选手" 维护一个序列 $a$，执行以下操作：

1.  `1 l r x` $\forall l\le i\le r,~ a_i=a_i+x$．
2.  `2 l r x` $\forall l\le i\le r,~ a_i=\max(a_i,x)$．
3.  `3 l r x` $\forall l\le i\le r,~ a_i=\min(a_i,x)$．
4.  `4 l r` 输出 $\sum\limits_{i=l}^r a_i$．
5.  `5 l r` 输出 $\max\limits_{i=l}^r a_i$．
6.  `6 l r` 输出 $\min\limits_{i=l}^r a_i$．

$n,m\le 5\times 10^5,~|a_i|\le 10^8$．所有类型 $1$ 操作有 $|x|\le 10^3$，其余操作满足 $|x|\le10^8$．

同样的方法，我们维护最大、次大、最大个数、最小、次小、最小个数、区间和．除了这些信息，我们还需要维护区间 $\max$、区间 $\min$、区间加的标记．相比上一道题，这就涉及到标记下传的顺序问题了．我们采用这样的策略：

我们认为区间加的标记是最优先的，其余两种标记地位平等．
对一个结点加上一个 $v$ 标记，除了用 $v$ 更新卫星信息和当前结点的区间加标记外，我们用这个 v 更新区间 $\max$ 和区间 $\min$ 的标记．
对一个结点取 $v$ 的 $\min$（这里忽略暴搜的过程，假定标记满足添加的条件），除了更新卫星信息，我们要与区间 $\max$ 的标记做比较．如果 $v$ 小于区间 $\max$ 的标记，则所有的数最后都会变成 v，那么把区间 $\max$ 的标记也变成 $v$．否则不管．
区间取 v 的 $\max$ 同理．

在维护信息的时侯，当只有一个数或两个数的时侯可能发生数集重合，比如一个数既是最大值又是次小值，需要特判．

cpp

--8<-- "docs/ds/code/seg-beats/seg-beats_2.cpp"

吉老师证出来这个算法的复杂度是 $O(m\log^2 n)$ 的．

???+ note "Mzl loves segment tree" 两个序列 $A,B$，一开始 $B$ 中的数都是 $0$．维护的操作是：

1.  对 $A$ 做区间取 $\min$
2.  对 $A$ 做区间取 $\max$
3.  对 $A$ 做区间加
4.  询问 $B$ 的区间和

每次操作完后，如果 $A_i$ 的值发生变化，就给 $B_i$ 加 $1$．$n,m\le 3\times 10^5$．

先考虑最容易的区间加操作．只要 $x\neq 0$ 那么整个区间的数都变化，所以给 B 作一次区间加即可．

对于区间取最值的操作，你发现你打标记与下传标记是与 $B$ 数组一一对应的．本质上你将序列的数分成三类：最大值、最小值、非最值．并分别维护（只不过你没有建出具体的最值集合而已，但这并不妨碍维护的操作）．因此在打标记的时侯顺便给 $B$ 更新信息即可（注意不是给 $B$ 打标记！是更新信息！）．查询的时侯，你在 $A$ 上查询，下传标记的时侯顺便给 $B$ 更新信息．找到需要的结点后，返回 $B$ 的信息即可．这种操作本质上就是把最值的信息拿给 $B$ 去维护了．另外仍要处理数集的重复问题．

???+ note "CTSN loves segment tree" 维护两个序列 $a,b$，执行以下操作：

1.  `1 l r x` $\forall l\le i\le r,~ a_i=\min(a_i,x)$．
2.  `2 l r x` $\forall l\le i\le r,~ b_i=\min(b_i,x)$．
3.  `3 l r x` $\forall l\le i\le r,~ a_i=a_i+x$．
4.  `4 l r x` $\forall l\le i\le r,~ b_i=b_i+x$．
5.  `5 l r` 输出 $\max\limits_{i=l}^r (a_i+b_i)$．

$n,m\le 3\times 10^5,~|a_i|,|b_i|,|x|\le 10^9$．

我们把区间 $[l,r]$ 中的备选答案 $A_i+B_i$ 分成四类：$A_i,B_i$ 均不是序列 $A,B$ 区间最大值、$A_i$ 是序列 $A$ 区间最大值但是 $B_i$ 不是序列 $B$ 区间最大值、$A_i$ 不是序列 $A$ 区间最大值但是 $B_i$ 是序列 $B$ 区间最大值、$A_i,B_i$ 均是序列 $A,B$ 区间最大值．我们不妨分别设为 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$．此外我们正常维护序列 $A,B$ 的区间最大值和次大值．下传区间加法标记和 $\min$ 标记时对 $A,B$ 最大值和次大值的处理与上述两个例题一致．对 $A$ 的 $\min$ 标记会影响到 $C_{1,1}$ 和 $C_{1,0}$，对 $B$ 的标记会影响到 $C_{1,1}$ 和 $C_{0,1}$．对 $A,B$ 的加法则会对 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ 均产生影响．只需要注意 $C_{0,0},C_{1,0},C_{0,1}$ 不存在的边界情况即可（例如区间 $[i,i]$ 只有 $A,B$ 的最大值与 $C_{1,1}$ 存在）．

接下来需要考虑在 pushup 时如何维护 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$．我们可以考虑一下完成 $A,B$ 最大值的更新之后，讨论左右儿子的 $A,B$ 最大值是否与当前节点 $A,B$ 最大值相等．我们以左儿子为例进行讲解，右儿子类似处理：

当左儿子的 $A,B$ 最大值与当前节点的 $A,B$ 最大值均相等时，左儿子的 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ 会分别对当前节点的 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ 产生贡献．
当左儿子的 $A$ 最大值与当前节点 $A$ 最大值相等，但是 $B$ 最大值不相等时，左儿子的 $C_{1,0},C_{1,1}$ 会对该节点的 $C_{1,0}$ 产生贡献，$C_{0,0},C_{0,1}$ 会对该节点的 $C_{0,0}$ 产生贡献．
当左儿子的 $A$ 最大值与当前节点 $A$ 最大值不相等，但是 $B$ 最大值相等时，左儿子的 $C_{0,1},C_{1,1}$ 会对该节点的 $C_{0,1}$ 产生贡献，$C_{0,0},C_{1,0}$ 会对该节点的 $C_{0,0}$ 产生贡献．
当左儿子的 $A,B$ 最大值与当前节点的 $A,B$ 最大值均不相等时，左儿子的 $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ 仅会对该节点的 $C_{0,0}$ 产生贡献．

区间查询结果的 $\max(C_{0,0},C_{1,0},C_{0,1},C_{1,1})$ 即为所求．

由于需要同时维护区间 $\min$ 和区间加法，所以复杂度仍是 $O(m\log^2 n)$．

cpp

--8<-- "docs/ds/code/seg-beats/seg-beats_4.cpp"

小结

在第本章节中我们给出了四道例题，分别讲解了基本区间最值操作的维护、多个标记的优先级处理、数集分类的思想以及多个分类的维护．本质上处理区间最值的基本思想就是数集信息的分类维护与高效合并．在下一章节中，我们将探讨历史区间最值的相关问题．

历史最值问题

历史最值不等于可持久化

注意，本章所讲到的历史最值问题不同于所谓的可持久化数据结构．这类特殊的问题我们将其称为历史最值问题．历史最值的问题可以分为三类．

历史最大值

简单地说，一个位置的历史最大值就是当前位置下曾经出现过的数的最大值．形式化地定义，我们定义一个辅助数组 $B$，一开始与 $A$ 完全相同．在 $A$ 的每次操作后，我们对整个数组取 $\max$：

$$ \forall i\in[1,n],\ B_i=\max(B_i,A_i) $$

这时，我们将 $B_i$ 称作这个位置的历史最大值，

历史最小值

定义与历史最大值类似，在 $A$ 的每次操作后，我们对整个数组取 $\min$．这时，我们将 $B_i$ 称作这个位置的历史最小值，

历史版本和

辅助数组 $B$ 一开始全部是 $0$．在每一次操作后，我们把整个 $A$ 数组累加到 $B$ 数组上

$$ \forall i\in[1,n], \ B_i=B_i+A_i $$

我们称 $B_i$ 为 $i$ 这个位置上的历史版本和．

接下来，我们将历史最值问题分成四类讨论．

可以用标记处理的问题

???+ note "CPU 监控" 序列 $A,B$ 一开始相同：

1.  对 $A$ 做区间覆盖 $x$
2.  对 $A$ 做区间加 $x$
3.  询问 $A$ 的区间 $\max$
4.  询问 $B$ 的区间 $\max$

每次操作后，我们都进行一次更新，$\forall i\in [1,n],\ B_i=\max(B_i,A_i)$．$n,m\le 10^5$．

我们先不考虑操作 1．那么只有区间加的操作，我们维护标记 $Add$ 表示当前区间增加的值，这个标记可以解决区间 $\max$ 的问题．接下来考虑历史区间 $\max$．我们定义标记 $Pre$，该标记的含义是：在该标记的生存周期内，$Add$ 标记的历史最大值．

这个定义可能比较模糊．因此我们先解释一下标记的生存周期．一个标记会经历这样的过程：

在结点 $u$ 被建立．
在结点 $u$ 接受若干个新的标记的同时，与新的标记合并（指同类标记）
结点 $u$ 的标记下传给 $u$ 的儿子，$u$ 的标记清空

我们认为在这个过程中，从 1 开始到 3 之前，都是结点 $u$ 的标记的生存周期．两个标记合并后，成为同一个标记，那么他们的生存周期也会合并（即取建立时间较早的那个做为生存周期的开始）．一个与之等价的说法是，从上次把这个结点的标记下传的时刻到当前时刻这一时间段．

为什么要定义生存周期？利用这个概念，我们可以证明：在一个结点标记的生存周期内，其子结点均不会发生任何变化，并保留在这个生存周期之前的状态．道理很简单，因为在这个期间你是没有下传标记的．

于是，你就可以保证，在当前标记生存周期内的历史 $Add$ 的最大值是可以更新到子结点的标记和信息上的．因为子结点的标记和信息在这个时间段内都没有变过．于是我们把 $u$ 的标记下传给它的儿子 $s$，不难发现

$$ Pre_s=\max(Pre_s,Pre_u+Add_s),Add_s=Add_u+Add_s $$

那么信息的更新也是类似的，拿对应的标记更新即可．

接下来，我们考虑操作 1．

区间覆盖操作，会把所有的数变成一个数．在这之后，无论是区间加减还是覆盖，整个区间的数仍是同一个（除非你结束当前标记的生存周期，下传标记）．因此我们可以把第一次区间覆盖后的所有标记都看成区间覆盖标记．也就是说一个标记的生存周期被大致分成两个阶段：

若干个加减操作标记的合并，没有接收过覆盖标记．
覆盖操作的标记，没有所谓的加减标记（加减标记转化为覆盖标记）

于是我们把这个结点的 Pre 标记拆成 $(P_1,P_2)$．$P_1$ 表示第一阶段的最大加减标记；$P_2$ 表示第二阶段的最大覆盖标记．利用相似的方法，我们可以对这个做标记下传和信息更新．时间复杂度是 $O(m\log n)$ 的（这个问题并没有区间对 $x$ 取最值的操作哦～）

cpp

--8<-- "docs/ds/code/seg-beats/seg-beats_3.cpp"