历史版本和 笔记

一、简要介绍

维护序列 $A$，支持下列几种操作：

• 给出 $l,r,x$，将 $A_{l\sim r}$ 加上 $x$。
• 记录一个版本，并复制一个新版本，以后的操作在新版本进行。
• 给出 $l,r$，求 $A_{l\sim r}$ 所有历史版本的和。

操作总数为 $m$。$n,m\le 5\times {10}^5$。

对于一个线段树节点，它的标记队列（就是将标记从前往后放入一个队列中）一定如下，其中 $v_i$ 对应一次区间加更新加的值，$\mathrm{memory}$ 对应记录版本的操作。

$$\{v_1,v_2,{\mathrm{memory}}_3,v_4,v_5,v_6,{\mathrm{memory}}_7,\dots \}$$

而对应那个时候即将下传的 tag 就是 $t_i=\sum _{i=1}^n{v}_i$。

记 $u$ 表示这个区间初始的和，$s{h}_i$ 表示操作完前 $i$ 个操作后的历史版本和。

$$\begin{array}{rl}s{h}_i& =\sum _{j=1}^i[q_j=\mathrm{memory}](u+t_j)\\ & =u\times (\sum _{j=1}^i[q_j=\mathrm{memory}])+\sum _{j=1}^i[q_j=\mathrm{memory}]t_i\end{array}$$

也就是说，记录 $\mathrm{memory}$ 出现的个数，记作 $c_i$；以及 $\mathrm{memory}$ 时的 $t_i$ 的和即可，将这个和记作 $s_i$。

每次更新时，先更新历史版本和，方法是让历史版本和加上未更新的和乘上 $c_i$，再加上 $s_i$；当前和再更新（$len$ 是当前区间长度，其他的变量而不是结构体成员的，都是来自父亲的信息）。

t[rt].sh += tc * t[rt].s + ts;
t[rt].s += tag * len;

接着考虑自己的 tag $c_1,s_1$ 怎么接受来自父亲的 tag $c_2,s_2$，考虑接受父亲的 tag 后，新的历史版本和 $s{h}^{\prime }$：

$$s{h}^{\prime }=u\times c^{\prime }+s^{\prime }=u(c_1+c_2)+s^{\prime }$$

根据线段树 tag 的定义，父亲的 tag 一定是比自己的 tag 的“更新时间”要晚，故 $s_2$ 代表的标记队列是接在 $s_1$ 以后的，所以 $s_2$ 中的 $c_2$ 个 $\sum t_i$ 都应该加上 $s_1$。

综上：

$$c^{\prime }\leftarrow c_1+c_2$$$$s^{\prime }\leftarrow s_1+s_2+c_2{s}_1$$

（变量而不是结构体成员的，都是来自父亲的信息）。

t[rt].tc += tc;
t[rt].ts += tc * t[rt].tag + ts;
t[rt].tag += tag;

二、刷题总结

1. P3246 [HNOI2016] 序列

解法 (1)

离线询问，对 $r$ 进行扫描线，线段树维护以 $r$ 为右端点时，每个左端点的最小值。

意思就是线段树的区间 $[l^{\prime },r^{\prime }]\in [1,r]$，维护的是 $[[l^{\prime },r^{\prime }],r]$ 的最小值的相关信息。

假设扫描线扫到 $r$，那么新进入一个 $a_r$，就是 $[[1,r],r]$ 的最小值对 $a_r$ 取 $min$，一个标准的 beats 操作。

当扫描到 $r$ 时，查询区间 $[l,r]$ 所有连续子序列的答案，先考虑固定左端点 $l$ 的情况，那么就是 $\sum _{i=l}^r\underset{j=l}{\overset{i}{min}}{a}_j$（也就是扫描到 $i$ 时，线段树维护的 $l$ 这一点的最小值）。

如果把扫描到的不同的 $r$ 看作若干个版本，固定左端点 $l$ 的子序列的答案，就相当于 $l$ 这一点的最小值的历史版本和。

那么不固定左端点 $l$，就是对 $[[l,r],r]$ 进行一次上面的操作，也就是求 $[l,r]$ 区间的最小值历史版本和就好了。

解法 (2)

由 NOIP 2024 T4，$a_r$ 能成为 $max$ 的区间，本质上就是往前找第一个比 $a_r$ 大的数 $a_l$，$[[l+1,r-1],r-1]$ 的最大值一定是 $a_l$，那么 $[[l+1,r],r]$ 的最大值就变成 $a_r$，使用一个单调栈，对区间进行加减即可解决，所以并不用 beats。

2. CF997E Good Subsegments

好区间换句话就是说 $(max-min)-(r-l)=0$ 的区间，所以直接维护那个式子的最小值和出现次数。

同理，离线询问，对 $r$ 进行扫描线，线段树也和上面的差不多，线段树里的 $[l^{\prime },r^{\prime }]\in [1,r]$ 表示 $[[l^{\prime },r^{\prime }],r]$ 的式子最小值。把不同的 $r$ 看成不同的版本。

$r$ 向右移动时增加了 $1$，故先给这一整个式子减小 $1$。然后用两个单调栈维护当前 $a_i$ 能够成为 $max/min$ 的区间，对这些区间的式子值进行修改。

然后同上题，求答案即可，答案就是 $[l,r]$ 内每一点最小值的出现个数的历史版本和。

为什么最小值就行了？易得 $[i,i]$ 时式子最小值是 $0$。

这题还有个牛逼的地方，很多题解都没讲：他没有加法标记。因为最小值个数由 push_up 决定，所以相当于它的标记队列全是 $\mathrm{memory}$，所以不用维护 $s_i$……

3. P10637 BZOJ4262 Sum

有一个经典的 $max/min$ 的转换：$min{a}_i=-max-a_i$，那么题目要求的就变成了：

$$\sum _{l\in [l_1,r_1]}\sum _{r\in [l_2,r_2]}(\underset{i\in [l,r]}{max}{a}_i+\underset{i\in [l,r]}{max}-a_i)$$

解决一个就可以解决另一个。

依旧考虑对 $r$ 进行扫描线，只需对 $r$ 进行差分，将答案变为 $[[l_1,r_1],r_2]$ 的答案减去 $[[l_1,l_2],l_2-1]$ 的答案即可。那么就变成了第一题。

4. P8868 [NOIP2022] 比赛

神题。

题目要求：

$$\sum _{p\in [l,r]}\sum _{q\in [l,r]}(\underset{i\in [p,q]}{max}\{a_i\}\times \underset{i\in [p,q]}{max}\{b_i\})$$

相当于上一题从加号变成了乘号。

考虑只算区间乘积，怎么做（$p,q$ 分别是 $a_i,b_i$ 的加法 tag，$l$ 是区间长度）。

$$\begin{array}{rl}\sum (a_i+p)(b_i+q)& =\sum a_i{b}_i+a_{i}q+b_{i}p+pq\\ & =(\sum a_i{b}_i)+q(\sum a_i)+p(\sum b_i)+pql\end{array}$$

将红色的部分当作 tag，做历史版本和即可。