请注意，此篇文章讲的是所有历史版本之和，而不是可持久化线段树维护区间和。

问题引入：

现在要求你维护两个个长度为 $n$ 的序列 $a$ 与序列 $s$，初始两序列均为 $0$，有 $q$ 次操作：

1. 将序列 $a$ 区间 $[l,r]$ 中的所有元素变为 $k$，每次此操作结束后，将 $s$ 序列中的所有 $s_i$ 加上 $a_i$。

2. 询问序列 $a$ 中 $[l,r]$ 的所有元素之和。

3. 询问序列 $s$ 中 $[l,r]$ 的所有元素之和。(即 $a$ 的历史版本和)

发现对一个线段树结点进行操作后，$sum_a’=k\times len$，$sum_s’=sum_s+k\times len$，直接对历史和进行区间加就能做。

问题引入 $2$：

现在要求你维护两个个长度为 $n$ 的序列 $a$ 与序列 $s$，初始两序列均为 $0$，有 $q$ 次操作：

1. 将序列 $a$ 区间 $[l,r]$ 中的所有元素加上 $k$，每次此操作结束后，将 $s$ 序列中的所有 $s_i$ 加上 $a_i$。

2. 询问序列 $a$ 中 $[l,r]$ 的所有元素之和。

3. 询问序列 $s$ 中 $[l,r]$ 的所有元素之和。(即 $a$ 的历史版本和)

$n\leq 10^6$，$q\leq 10^6$，$a_i\leq 10^9$。

法一：

考虑到 $s_i$ 是由各个版本的 $a_i$ 加起来的，其必然与时间戳有关，于是我们设 $t$ 为操作一的当前执行数量。

每当执行操作一时，对于线段树上的某个节点有 $sum_a\leftarrow sum_a+k\times len$，$sum_s\leftarrow sum_s+sum_a$。

分开来看，有 $sum_a’=sum_a+k\times len$，$sum_s’=sum_s+sum_a+k\times len$，显然后者有个 $sum_a$ 使得我们的操作变得棘手，不好维护，但我们可以利用时间戳的性质：
$$ sum_s=t\times sum_a-((t-t)\times k+(t-t’)\times k’+(t-{t’‘})\times {k’‘}.....)\times len $$
于是我们只要设：
$$ c=(t+1)\times sum_a-sum_s=(t\times k+t’\times k’+{t’‘}\times {k’‘}.....)\times len $$
这样式子里面就没有动态变化的东西了，考虑维护，显然每当加 $k$ 时，$c$ 将会加上 $t\times k$。

询问时求 $sum_s=(t+1)\times sum_a-c$ 即可。

时间复杂度：$O(q\log n)$。

法二：
矩阵乘法，考虑设计以下矩阵乘法(状态矩阵与转移矩阵):
$$ \begin{bmatrix} s,sum,len \end{bmatrix} \begin{bmatrix} 1,0,0\\1,1,0\\k,k,1\end{bmatrix}= \begin{bmatrix} s’,sum’,len’ \end{bmatrix} $$
直接用线段树维护矩阵即可。

时间复杂度：$O(q\log n\times 3^3)$。

例题一：CF997E Good Subsegments。

例题二：NOIP2022 比赛。