《区间最值操作与历史最值问题》（吉如一）阅读笔记

A. 基础区间最值操作

问题描述

给定一个序列 \(A\)，需要支持以下操作：

1. 给定区间，将内部所有元素对 \(X\) 取最大值。
2. 询问区间和。

解法

首先，传统的线段树区间操作时间复杂度为 \(\Theta(\log n)\)，这是基于任何一个区间在线段树上作拆解，最终得到的所有节点个数为 \(\log n\) 级别。然而，对一个区间进行区间最值操作以后，这个区间的和不能通过维护某些信息来快速得到。所以我们必须递归处理，这样复杂度没有保证。

认真观察一下这个问题，发现它其实是一个类似“区间条件赋值”的东西，根据类似珂朵莉树一些问题的经验，这种题目基于颜色种类数势能分析一下往往可以让复杂度对。所以考虑对某个节点的一次向下递归起码要让这个节点所对应的区间内颜色种类数减一。对于这样的要求，首先可以考虑如果区间最小值大于 \(X\)，那么不继续递归。然而这样不能满足条件，因为有可能修改只涉及到区间内的一种数值——即区间最小值。对于这种情况，考虑记录区间内的严格次小值，这样，如果修改只涉及到区间内的最小值，就可以停止递归，只需要记录最大值个数即可。

现在证明这样做的复杂度是对的。显然地，向下进行一次递归消耗 \(\Theta(1)\) 的时间，同时会使得当前区间内的颜色种类数减一。将所有节点子树内的颜色种类数之和作为势能，那么初始序列的势能是 \(\Theta(n \log n)\)；进行一次区间操作增加的势能是 \(\Theta(\log n)\)（只有一开始拆分区间时访问到的节点势能会增加）；下推标记增加的势能是 \(\Theta(1)\)（不可能再次触发递归）。所以总复杂度是 \(\Theta((n + q) \log n)\)。实际上，区间条件赋值都可以类似这样设计，即强制某次高消耗的操作一定会减少区间内的颜色数。

B. 区间最值+区间加

问题描述

给定一个序列 \(A\)，需要支持以下操作：

1. 给定区间，将内部所有元素对 \(X\) 取最大值。
2. 给定区间，将内部所有元素增加 \(X\)（可能为负）。
3. 询问区间和。

解法

加入了区间加的操作，那么能不能按照原来的做法去做呢？考虑单次区间加对于势能函数的影响。注意到单次区间加可能让在区间内外都有分布的颜色分裂成两种，这对势能函数的影响是灾难性的，所以先前的势能分析不再有效。但是似乎也不能卡满？考虑其他证明思路。

考虑这样刻画区间严格次小值：对于一个线段树节点，取它区间内的最小值作为标记。如果标记和父亲的标记相同就删除这个标记。那么任何点的标记比祖先的标记更大，区间严格次小值就是子树内（不包括自身）的最小标记。考虑标记的总个数。一开始标记只有 \(\Theta(n)\) 个，每一次区间取最大值操作或者区间加操作都可能带来 \(\Theta(\log n)\) 个新的标记。这是因为只有在线段树上拆分区间时经过的节点才可能额外增加标记：对于取最大值操作，向下递归会消耗标记；对于区间加，某个子树内整体加减并不影响某个点的标记存在与否。所以在全过程中出现的标记总个数是 \(\Theta(n+m\log n)\)。

现在分析取最大值操作时向下递归操作的时间开销。首先，向下递归说明子树内存在至少一个标记使得标记数值小于 \(X\)。容易得出，所有这样的标记在递归结束以后都会被删除。但是不能说向下递归一次就会删除一个标记！这是因为某个要删除的标记标记上方可能有一条长链，上面都没有标记，在这个长链上向下走可能消耗 \(\Theta(\log n)\) 的时间，然而只删除一个标记。所以这一部分，时间复杂度只能分析到 \(\Theta(n\log n+m\log^2n)\)。可惜吉老师同样不能将这个复杂度卡满。直觉和实践告诉我们，它在一般数据下表现得像单 \(\log\)。

C. 区间取最大+取最小

问题描述

给定一个序列 \(A\)，需要支持以下操作：

1. 给定区间，将内部所有元素对 \(X\) 取最大值。
2. 给定区间，将内部所有元素对 \(X\) 取最小值。
3. 询问区间和。

解法

直接参考问题 A 即可，记录区间最大、次大、最小、次小。吉老师这里说是双 \(log\)，他的证明方式可能不太合适。实际上用区间颜色数做势能就可以直接分析到单 \(\log\)。这个问题比较不重要，因此略过不谈，只是顺带提一下复杂度的问题。

第一部分·小结

以上的思路，即将区间最值操作转化为对最值的区间加操作，正是 Segment Tree Beats 的基础。它的复杂度正确性依赖于对区间最值操作的势能分析。实际上，双 \(\log\) 势能分析的正确性只依赖于对区间整体操作可以保留原有顺序（甚至可以不满足此要求，只需要确保整体区间操作不会增加标记数目或增加数目为常数），因此这一做法其实很有扩展性。此外，这种势能分析非常难卡，在实践中可以视为单 \(\log\)。

接下来，基于“划分区间最值与非最值转化问题”的基本思想，还可以利用这一算法解决一系列更为复杂的问题。

D. 区间最值+区间加+区间修改记录

这个问题比较简单，但是也很基础。

问题描述

给定一个序列 \(A\)。维护数组 \(B\)，满足一开始 \(B_i = 0\)，接下来每一次操作中，如果 \(A_i\) 发生改变，那么 \(B_i\) 增加 \(1\)。需要支持以下操作：

1. 给定区间，将内部所有元素对 \(X\) 取最大值。
2. 给定区间，将内部所有元素对 \(X\) 取最小值。
3. 给定区间，将内部所有元素加上 \(X\)（可能为负）。
4. 询问区间和。（以上均针对 \(A\)）
5. 询问 \(B\) 的区间和。

解法

通过维护的区间最大、次大、最小、次小数的信息，可以将 \(A\) 的元素分为三类：最大值、最小值、其他值。每一次操作都是对区间内某一类数整体进行操作。记录这些数的个数，则区间修改对 \(B\) 的影响很好计算。

需要讨论区间内颜色数小于 \(3\) 的情况。

双数组区间加+区间最值 维护和的最值

问题描述

给定两个序列 \(A, B\)，需要支持以下操作：

1. 给定区间，将内部所有 \(A\) 的元素对 \(X\) 取最大值。
2. 给定区间，将内部所有 \(A\) 的元素增加 \(X\)（可能为负）。
3. 给定区间，将内部所有 \(B\) 的元素对 \(X\) 取最大值。
4. 给定区间，将内部所有 \(B\) 的元素增加 \(X\)（可能为负）。
5. 询问区间内 \(A_i + B_i\) 的最大/小值。

解法

参考上述的分类思想，可以将一个线段树节点区间内的数按照是不是 \(A\) 区间最值、是不是 \(B\) 区间最值分为四种分别维护。合并儿子时考虑当前区间 \(A,B\) 序列最值的来源进行讨论。

Bonus：\(K\) 个序列

时间 \(\Theta((nk+q)2^k\log n)\)，空间 \(\Theta(n2^k)\)。纯纯垃圾。但是我还不会更好的东西！请大家耐心等待。

区间最值+区间加+区间 \(\gcd\)

问题描述

给定一个序列 \(A\)，支持以下操作：

1. 给定区间，将内部所有元素对 \(X\) 取最大值。
2. 给定区间，将内部所有元素增加 \(X\)（可能为负）。
3. 询问区间 \(\gcd\)。

解法

首先，区间加区间 \(\gcd\) 怎么做？注意到我们并不会做全局加全局 \(\gcd\)，所以必须做一些转化。实际上，\(\gcd(a_1, a_2, \dots, a_n) = \gcd(a_1, a_2 - a_1, \dots, a_n - a_{n-1})\)，所以我们可以维护差分序列。那么只需要支持单点加区间 \(\gcd\) 即可。

接下来咕咕咕了。