Segment Tree Beats 学习笔记

chkmin 线段树、历史值问题。

CF1290E

将题意转化为求 \(\sum\limits_{i=1}^n (suf_i-pre_i-1)\)，其中 \(suf_i\) 表示 \(i\) 后第一个比 \(i\) 大的数的位置，\(pre_i\) 表示 \(i\) 前第一个比 \(i\) 大的位置。这等价于求 \(\sum\limits_{i=1}^n pre_i\)，剩余部分是对称的。

直接做是 \(\mathcal{O}(n^2)\) 的，考虑 \(k\) 从小到大增量维护每个 \(pre_i\)，每次的操作是加入一个数，对原序列的影响是：一个后缀的 \(pre_i\gets \max(x,pre_i+1)\)，其中 \(x\) 是加入这个数在当前序列中的排名。把操作拆成一次区间加可以一次 chkmax，采用线段树维护即可。

具体地，每个结点维护 \((sum,mn_1,mn_2,c,mnc)\)，表示和、最小值、次小值、数的个数、最小值个数，并维护标记 \((tg,mtg)\) 表示全局加值和对最小值加值。每次若一个操作只对最小值有作用，就对所有最小值整体打上一个加法标记，否则两边递归即可。利用区间内不同数个数作为势能可以分析复杂度正确。

“二重奏”

题意

维护两个序列 \(a,b\)，支持：

• 对 \(a\) 区间 chkmin / 对于 \(b\) 区间 chkmin。
• 对 \(a\) 区间加 / 对 \(b\) 区间加。
• 查询区间 \(a_i+b_i\) 的最大值。

思路

来源：cmd 的博客

仍然采用类似的维护方法。发现我们对于一个区间的操作只有：对区间 \(a\) 的最大值加值，对区间 \(b\) 的最大值加值。考虑再次基础上维护出 \(a_i+b_i\) 的最大值，只需要维护出四个最小值，即：\(a_i\) 是区间最小值且 \(b_i\) 是区间最大值 / \(a_i\) 是区间最大值但 \(b_i\) 不是区间最大值 / \(a_i\) 不是区间最大值但 \(b_i\) 是区间最大值 / \(a_i,b_i\) 均为区间最大值。不难在修改的过程中维护出这四个值的变化。

P6242

关键问题在于怎么处理区间修改，更具体地，是怎么处理“标记队列”对整个区间的影响，并将它归纳为 \(\mathcal{O}(1)\) 个变量，因为一般而言只有在下放标记的时候把标记合并才能保证标记数量的规模正确。

体现在历史最值上面是简单的，我们要求出的是 \(\max\limits_{i=1}^n\left(a_x+\sum\limits_{j=1}^i t_j\right)\)，其中 \(t_j\) 表示第 \(j\) 个加法标记的取值，把前面提出来就可以知道我们实际上只要在标记里面维护 \(\max\limits_{i=1}^n\sum\limits_{j=1}^i t_j\)，合并标记是简单的。

P3246

历史版本和。

考虑每个最小值的贡献，假设一个位置在 \([L_i,R_i]\) 处是最小值，那么区间 \([L_i,i]\times [i,R_i]\) 会有 \(a_i\) 的贡献，每次查询是查 \([l,r]\times [l,r]\) 的贡献和。这个可以抽象成矩形加，矩形求和的问题，使用历史版本和维护即可。

历史版本和和上面的逻辑差不多，大概是每做完一轮加法之后打一个历史和标记，然后考虑标记队列的影响。

感觉我目前见过的历史版本和都是维护矩形加矩形求和用的。

CF997E

混进了奇怪的东西，而且这个题我不会？？？

考虑扫描线，每次处理每个右端点的贡献。区间 \([l,r]\) 合法的条件是 \(\max[l,r]-\min[l,r]=r-l\)，也就是说需要对所有 \(\max[l,r]-\min[l,r]+l=r\) 的 \(l\) 操作，一个经典的观察是等于的一定是最小值，所以一个贡献相当于对所有最小值 \(+1\)，维护区间最小值个数即可快速维护。

所以为啥题解在说历史和，不懂。

P8868

单调栈之后就是一个区间加 / 维护 \(\sum a_ib_i\) 历史和的问题。按照上面的方法随便推一下标记就好了。

亏麻了。