9
吉司机线段树/历史最值
(ps：之前写过线段树总结，现在觉得这块内容放这个板块较为合适。)
很久以前用一知半解态度过的模板题，现在重新学习了下，不算难。
我的文章风格可能都有点刨根问底的感觉，理解的层次至少会阐述正确性（而不是说做法然后直接放代码）。
阅读门槛是需要知道线段树，标记合并。其实很低，如果势能分析看不懂也没关系。
PART1 区间最值操作
吉司机这个东西是可以在对数平方时间内维护区间最值修改的，操作如同：
* 对 [l,r][l,r][l,r] 中的所有数执行 ai→min(ai,k)a_i \to \min(a_i,k)ai →min(ai ,k)，其中 kkk 是给定常数。
当然上面的 min\minmin 换成 max\maxmax 也是完全可以的，我们先来阐明一下解决思路，再考虑时间复杂度的具体分析。
针对取 min\minmin 操作进行讨论，另外的取 max\maxmax 操作是完全对称的。在此基础上如果只需要查询最值则可以简单做到 O(nlogn)O(n \log n)O(nlogn)，但这只是单纯的利用最值标记实现的简单线段树，并不是我们今天所讨论问题。所以，我们同时还需要支持查询区间总和等相关问题。
我们先明白查总和相对查最值更难做的原因，其实在于总和信息和取最值是没有结合律等优良性质的，刚刚所谈论的最值好做是因为操作和查询本身就支持信息合并。
更简单的说，单次修改中总和的修改量不能快速通过标记合并快速维护。所以我们必须考虑转化问题，这是线段树维护复杂信息的常见思路。本质在于让原问题变成更常见的问题，然后就可以很轻松地处理原问题。
一个简单的优化是跳过最大值小于等于 kkk 的节点，然而是不好直接做修改的。将问题转化为最小值大于等于 kkk 就做区间推平，特判叶子节点的想法。其实是完全不行的，因为最坏情况所有区间叶子都会被修改一次，修改总量完全没有保证，和暴力没有本质不同。所以我们需要做一个相对合理的批量修改方法。
换另一个可能更好的想法：维护最大值 maxnmaxnmaxn，最大值个数 cntcntcnt，严格次大值 sesese。修改的时候同样跳过最大值小于等于 kkk 的节点，并且当可以修改的节点满足 se<k≤maxnse < k \le maxnse<k≤maxn 就直接打删除标记 mul=k−maxnmul = k-maxnmul=k−maxn。这里表示将最大值区间加 mulmulmul，实际上效果相当于把最大值改成 kkk。维护一个标记 tagxtag_xtagx 表示当前节点 xxx 的最大值需要加多少就可以了，更新总和的时候贡献就是 tagx∗cnttag_x * cnttagx
∗cnt。
这里其实我们可以发现一件事情：最大值被单独列出维护了一个标记。这意味着如果还需要支持其他操作：比如区间加。则我们必须要维护两套标记：一个是针对最大值的，一个是针对除最大值以外的所有数。
其实底层原因也很简单，就是因为最大值对于的区间加标记不会作用于其它数上，就导致最大值所需要考虑的信息更多，当然如果这些信息不会影响到某种标记合并也可以分开维护。
首先考虑两个问题：答案正确性和时间复杂度分析。答案的正确性是比较显然的，接下来考虑时间复杂度的分析。这里其实直接分析单次修改是很容易绕弯子的，事实上证明用了一个高级技巧：势能分析。
在这里我会尽量用文字阐述下证明思路和过程，这里我们引入一个概念函数 W(u)W(u)W(u)，其满足以下性质：
* 当节点 uuu 的最大值不等于其父亲节点的最大值时，有 W(u)=1W(u) = 1W(u)=1。
* 否则都有 W(u)=0W(u) = 0W(u)=0。
因为我们访问节点 uuu 需要的代价实际上是还需要考虑深度，换句话说总势能在 O(nlogn)O(n \log n)O(nlogn) 量级，也就是 ∑W(x)×depx\sum W(x) \times dep_x∑W(x)×depx ，这里一个节点的深度可以粗略的看做 logn\log nlogn。
然后我们考虑分析修改操作对势能总和的相对影响，这个所谓的势能实际上可以简单认为它等于程序总运行次数（也就是时间复杂度总量）。
至于根本原因，完全可以这样理解：
* 考虑一个节点 xxx 满足 W(x)=0W(x) = 0W(x)=0，我们发现此时必然满足 maxnx<maxnfxmaxn_x<maxn_{f_x}maxnx <maxnfx ，此时 maxnxmaxn_xmaxnx 只能贡献到 sefxse_{f_x}sefx 。又因为此时暴力递归必有 sefx<kse_{f_x} < ksefx <k，所以我们知道 xxx 这个节点不可能会被暴力递归访问到，访问它的时间复杂度是 O(logn)O(\log n)O(logn) 级别的，所以我们就依据这个性质设计势能函数值为 W(x)×depxW(x) \times dep_xW(x)×depx 。
同时，只需要聚焦于因为值域问题暴力递归处理节点的情况。其他情况就是普通线段树的时间复杂度。
回到势能分析中，当节点 xxx 的次大值 sesese 大于等于 kkk 时，我们显然有：
* 两个子节点 lsxls_xlsx 和 rsxrs_xrsx 的最大值一定大于等于 kkk。
* 其中一定有一个孩子（不妨设为 rsxrs_xrsx ）的最大值小于 xxx 的最大值，否则如果两个子节点最大值都等于 maxnxmaxn_xmaxnx ，则次大值不可能 ≥k\ge k≥k。除非子树内有更深的分裂，这会在继续递归的儿子中被讨论，这里直接认为就是满足条件的。
当我们在该子树执行完操作并向上回溯后：
* lsxls_xlsx 和 rsxrs_xrsx 的最大值由于被 kkk 截断，现在全部变成了 kkk。
* 父亲节点 xxx 的最大值也更新为 kkk。
* 此时，由于 maxnrsx=maxnx=kmaxn_{rs_x} = maxn_{x} = kmaxnrsx =maxnx =k，原本不相等的最大值现在对齐了。于是，W(rsx)W(rs_x)W(rsx ) 从 111 变成了 000。
势能减少了，严格来说减小的势能实际上是 deprsx=depx+1dep_{rs_x} = dep_x+1deprsx =depx +1。
由于 xxx 是暴力递归节点，虽然我们在当前层花费了 O(1)O(1)O(1) 的常数时间，但我们成功让一个深度为 depx+1dep_x+1depx +1 的节点的 WWW 归零，释放了 depx+1dep_x+1depx +1 的势能。同时也可以通过这个方面说明每一次暴力递归都可以在后续递归中找到某个节点，让它势能 WWW 归零来为时间复杂度的开销买单。
同时还需要分析区间加操作带来的势能变化，一共会拆成 log\loglog 个节点，最坏情况下每个节点 xxx 的父亲 fxf_xfx 的另一个儿子的势能由 000 变成 111，总变化量量级至多为 O(qlog2n)O(q \log ^2 n)O(qlog2n)。并且加标记下传不会影响势能 WWW 变化，增减势能的情况就上面两种。
势能总量为 O((n+q)log2n)O((n+q) \log^2 n)O((n+q)log2n) 量级，单次操作会增加或消耗 O(log2n)O(\log ^2 n)O(log2n) 的势能，总时间复杂度自然为 O((n+q)log2n)O((n+q) \log ^2 n)O((n+q)log2n)。
当时吉老师的论文如果我没记错的话是修改的势能分析错判为 O(logn)O(\log n)O(logn)，并且其实势能增量卡慢其实不简单，所以实际表现和常数大一点的 O(nlogn)O(n \log n)O(nlogn) 没什么区别。
PART2 历史最值
这块部分严格来说和最值修改完全没关系，一个位置的历史最值的定义是该位置上的数在所有时刻中的最值。相对吉司机要简单很多。
同样的，我们考虑历史最大值的做法，记 AiA_iAi 表示当前时刻位置 iii 上的值，BiB_iBi 表示所有时刻位置 iii 的最大值。实际上我们是在维护的历史最大值可以看做一个前缀时间内数的最大值。
首先我们要维护的区间历史最值显然只会被区间最大值更新，换到线段树上就是考虑标记的合并与迭代。只维护加标记 tag1tag_1tag1 的想法是错误的，原因在于标记可能经过多次合并，实际意义就是加了很多次数。我们一定会考虑维护 tag1tag1tag1 的历史最大值，记作 tag2tag2tag2,用它来更新答案。
由于标记下传后贡献已经清除，所以本质上我们只是在维护：
* tag1tag1tag1 表示上一次下传标记后到现在的加标记。
* tag2tag2tag2 表示上一次下传标记后到现在的时刻中，tag1tag_1tag1 的最大值。
同时记最大值为 m1m_1m1 ，历史最大值为 m2m_2m2 。考虑下传节点 xxx 的标记：
* tag1sonx→tag1sonx+tag1xtag1_{son_x} \to tag1_{son_x} + tag1_xtag1sonx →tag1sonx +tag1x ，加标记合并。
* tag2sonx→max(tag2sonx,tag2x+tag1sonx)tag2_{son_x} \to \max(tag2_{son_x},tag2_x+tag1_{son_x})tag2sonx →max(tag2sonx ,tag2x +tag1sonx )，理由很简单，此时 xxx 标记对 sonxson_xsonx 的影响在于 tag1xtag1_xtag1x ，而由于我们维护的 tag1xtag1_xtag1x 实际上是一个时间点的加标记，换句话说是落在该节点的加操作之和。本质上我们应该遇到一个操作就直接下传儿子修改，但是为了复杂度我们选择了延迟下传，所以就会选择使用
tag2xtag2_xtag2x 更新。正确性只需要考虑 tag2xtag2_xtag2x 合法（一定是某个时刻的 tag1xtag1_xtag1x ）并且最优（根据定义它最大）。
然后依据历史最大值标记的最大贡献 tag2x+m1(x)tag2_x+m1(x)tag2x +m1(x) 取更新 sonxson_xsonx 的 m2m_2m2 即可。整个过程的设计思路比较自然。
PART 3 结合问题
模版题把两个问题合并在了一起，实际上做法还是依据上述思路维护线段树信息，之前在第一部分我也顺便提到过：由于吉司机把最大值单独考虑，所以要针对最大值和非最大值设计两种标记组。
什么意思，就是实际上我们需要维护四个标记 tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4，但是其实是因为 tag1,tag2tag1,tag2tag1,tag2 服务于区间最大值（定义同第二部分），其余的 tag3,tag4tag3,tag4tag3,tag4 服务于其余所有数，本质上只是迫不得已维护了两套一模一样的标记而已。
这段代码是在处理节点 xxx 加入的四个标记分别为 v1,v2,v3,v4v1,v2,v3,v4v1,v2,v3,v4 后的影响。首先更新和，考虑最大值个数和其余数个数（里面 clenxclen_xclenx 是节点 xxx 代表的线段树区间长度）和标记组合即可。剩下的都是刚刚推导里面就有的，注意这里需要判断次大值是否存在的情况。
然后考虑标记下传函数：
这段代码考虑了 W(sonx)W(son_x)W(sonx ) 的情况，也就是说我们需要考虑某个儿子的最大值是不是节点 xxx 的最大值，如果不是则不需要考虑最大值标记信息不同带来的影响。因为下传的 tagtagtag 是以节点 xxx 的视角设计的，下传到 sonxson_xsonx 需要变换成 sonxson_xsonx 的视角，也就是说如果 $son_x $ 本身对最大值没贡献则会被自动规约到 tag3x,tag4xtag3_x,tag4_xtag3x ,tag4x 的管辖范围。
关键代码如下：
当然如果操作需要支持取最大值或者最小值，维护思路完全一样。但是值得注意的一点是注意特判重复贡献。理论上维护三套标记的话其中两套分别是为最大值和最小值服务的，但是如果一个数同时是最大值和最小值需要特别判断。除此之外，也需要考虑最大值同时是次小值，最小值同时是次大值的情况（不然非最值标记会重复贡献）。
总而言之这是一个相对高级的线段树技巧，但是理解起来也不是特别困难。
有帮助，赞一个