一些铺垫。
定义幺半群，就是 \((S, *)\) 满足结合律并且存在单位元，线段树维护的信息需要是幺半群信息。这里需要单位元是因为初始应该被赋值成单位元。
懒标记同样也要是幺半群，并且懒标记操作对于维护的值的幺半群要产成幺半群作用。也就是要满足可以将懒标记合并，且对整个区间操作等价于操作左右子区间再合并。
区间最值问题
要求区间取 \(\min\)，查询区间最大值，区间和。
根据上文会发现这里是可以打 tag 的，但如果直接打 tag 的话 pushdown 的复杂度爆了。然而我们会发现对 \(x\) 取 \(\min\) 的时候只会影响比 \(x\) 大的数，这启发我们记录最大值 \(mx1\) 和次大值 \(mx2\)（其实并没有那么启发）。为了方便维护和，我们还要记录最大值的数量。
我们分类讨论：
- 若 \(x \geq mx1\)，没有影响。
- 若 \(mx2 < x < mx1\)，那么我们只需要将最大值更新一下即可。
- 若 \(x \leq mx2\)，那么我们直接递归。
根据吉如一老师的集训队论文，一次 modify 是 \(\log n\) 的。下面给出证明。
我们将每个结点维护的最大值看作一个标记，如果一个结点的标记与父亲相同我们就删去标记，类似下图，容易发现标记虽深度递减且一个结点的次大值就是孩子标记的最大值。
我们的一次 DFS 更新相当于在子树中回收掉大于它本身的标记，也就是复杂度所在。将一次取 \(\min\) 操作产生的标记看作同一类，定义一个标记类的权值为所有子树中存在这一类标记的点的个数。定义势能函数 \(\phi\) 为线段树中所有标记类的权值总和。
对于一次取 \(\min\) 操作，添加一个新的标记类，权值显然是 \(O(\log n)\) 的，势能贡献总和是 \(O(q\log n)\) 的。
对于一次 pushdown，我们让这一类标记权值增加了 \(O(1)\)，势能贡献总和是 \(O(q\log n)\) 的。
注意，我们做 DFS 操作肯定是因为当前子树内有标记回收，所以如果我们经过一个结点时回收了标记那么一定会使势能减少 \(1\)。
于是总共势能的变化是 \(O(q \log n)\)，而总复杂度为 \(\sum c_i + \Delta\phi\)。这里的 \(\sum c_i\) 显然是显著小于势能变化的，所以我们可以得到总复杂度就是 \(O(q \log n)\)，于是均摊完单次操作就是 \(O(\log n)\)。
再拓展一点，考虑加上区间加的操作。那么大体做法是不变的，因为该维护的还是可以维护，只需要多加一个加法的 tag 即可。
根据吉老师的证明，复杂度是 \(O(q\log^2n)\) 的，但实际效率接近 \(O(q\log n)\)，需要对上述分析过程进行一些调整，这里不多叙述（其实是我不想看了）。
值得注意的是，论文中对于加上区间加操作的证明并没有用到区间加的性质，这意味着我们将区间加换成一些别的东西复杂度也是相同的。
不妨考虑我们对于区间取 \(\min\) 的做法的本质是什么。
其实我们将区间最值转化成了区间加减。我们的做法将区间中的数分为了最大值和非最大值两类，分别处理对于最大值加上或减去一个数与对于非最大值加上或减去一个数。
于是我们得到了以小常数 \(O(\log n)\) 复杂度将区间最值转化为区间加减的方法。
考虑这样的一个问题：要求支持对 \(A\) 区间取 \(\min\)，区间取 \(\max\)，区间加。每次如果 \(A_i\) 发生变化则 \(B_i \leftarrow B_i + 1\)，查询 \(B\) 的区间和。
如果没有 \(\min\) 和 \(\max\) 那么是简单的，只要 \(x \not = 0\) 就加一。有了 \(\min\) 和 \(\max\) 后，我们考虑将区间分成最大值、最小值、其它元素来维护，也就是转化为区间加减。
另一个问题：对于 \(A, B\) 分别维护区间 \(\min\)，区间加，询问 \(A_i + B_i\) 的最大值。
维护四种分类，分别是同时在 \(A, B\) 中取到最大值，只在 \(A\) 取到，只在 \(B\) 取到，完全不取到。
不难拓展到 \(K\) 个数组的情况，复杂度是 \(O(q2^k \log n)\)。
一个很难的问题：区间取 \(\min\)，区间加，区间 \(\gcd\)。
如果没有取 \(\min\) 那就是简单的，现在有取 \(\min\) 那我们不妨分成最大值和非最大值两部分，我们维护 \(s, t\) 表示非最大值序列中数值的最小和最大值。合并时，假设 \(mx_{lc} > mx_{rc}\)，那么新的 \(g = \gcd(g_{lc}, g_{rc}, s_{rc} - t_{lc}, mx_{rc} - t_{rc})\)，复杂度是 \(O(q\log^3n)\) 的。
区间历史最值
其实写这一篇的本意就是学习这个，这里会从我比较喜欢也更本质的矩阵角度讲解。
例题：P6242，要求维护区间加，区间取 \(\min\)，查询区间和，区间最大值，区间历史最大值。
考虑令矩阵转移为 \(C_{i, j} = \max\{A_{i, k} + B_{k, j}\}\)，显然是个幺半群。
我们维护向量序列 \(\begin{bmatrix} a_i \\ b_i \end{bmatrix}\)，那么一次区间加操作可以转化为：
更新区间历史最大值同理，区间最大值也是好解决的，就是向量加法，区间和就更基础了。
考虑区间取 \(\min\) 怎么办，我们可以使用区间最值问题的套路，分成最大和次大两种维护即可。
来看更多的例题。
例题：P4314，维护区间加，区间赋值，查询区间最大值，区间历史最大值。
区间加我们会，区间赋值怎么办呢？由于要把 \(a\) 变成 \(k\)，所以需要在向量中多开一维 \(0\) 辅助转移即可。
但这样我们需要 \(3 \times 3\) 的转移矩阵，常数有点爆炸。我们会发现常数瓶颈在懒标记下传时的矩阵乘法上，注意到矩阵中很多位置都是确定的 \(0\) 或 \(-\infty\)，于是我们只需要维护一些特殊位置然后手动进行矩阵乘法即可。
例题：P8868，要求 \(\sum_{L \leq l \leq r \leq R} \underset{l \leq i \leq r}{\max}{a_i}\underset{l \leq i \leq r}{\max}{b_i}\)。
考虑离线下来 \(r\) 从 \(1 \to n\) 处理询问，则我们需要维护 \(l\) 的历史和。
先考虑 \(r\) 对与最大值的影响，可以通过单调栈得到影响的区间将区间赋值转化为区间加。
那么我们不妨维护矩阵 \([a, b, ab, c, len]\)，其中 \(c\) 为历史和，\(ab\) 为乘积和。那么转移矩阵是好构造的。
注意我们维护转移矩阵的时候某些原本为 \(0\) 的东西可能会改变，一共需要维护 \(9\) 个值。
这部分篇幅还是比较简短，因为矩阵公式打起来太麻烦了，就省略了很多具体的转移矩阵推导，看不懂的可以去看题解 awa。
最后给大家喵一声，喵呜meow~