【题解】AtCoder abc322_f Random Update Query-526互联

传送门：https://atcoder.jp/contests/abc332/tasks/abc332_f

容易发现，对于一个位置 $i$，$A_i$ 的最终值是由对 $i$ 的最后一次赋值操作决定的；因此，将所有操作按时间顺序倒过来考虑，则由第 $j$ 次操作决定 $A_i$ 最终值的概率为"在第 $(j+1)$~$m$ 次操作中没有修改过 $i$ 的概率"与"第 $j$ 次操作修改 $i$ 的概率"乘积；

此处提供两种思路：

第一种：

基础思路：按照倒转后的操作顺序，每次统计一个操作对于所有 $i$ 答案的贡献；

记第 $i$ 个位置截至目前仍未被修改的概率为 $hvp_i$、该位置答案为 $ans_i$；设第 $j$ 次操作为随机将 $[l,r]$ 中任意一个位置的值修改为 $x$，则对于所有 $i\in[l,r]$，我们要令 $ans_i=ans_i+hvp_i*\frac{1}{r-l+1}*x，hvp_i=hvp_i*\frac{r-l}{r-l+1}$（二者同时进行，没有先后顺序）；

此时，对于这样“每个位置有多个参数，每次要在连续一段位置的每个参数组自身内部做变换”的问题，我们可以联想到线段树维护矩阵乘法，每次操作就相当于给一段连续位置乘上同一个矩阵；（注：此处推荐另一道非常相似但是强于本题的题目：https://www.luogu.com.cn/problem/P7453）

刚才我们的操作，可以转换为：

$\left| \begin{array}{cccc} hvp_i & ans_i \end{array} \right| $ $*=$ $\left| \begin{array}{cccc} \frac{r-l}{r-l+1} & \frac{1}{r-l+1}*x \\ 1 & 0 \end{array} \right| $

此时我们就有了做法：维护一棵 $n$ 个点的线段树，线段树的每个节点上是一个矩阵，位置 $i$ 的初始值为 $\left|

\begin{array}{cccc}

hvp_i & ans_i

\end{array}

\right| $；将所有操作的顺序倒过来，每次对于操作范围 $[l,r]$，在线段树上给 $[l,r]$ 区间内每个矩阵都乘上一个$\left|

\begin{array}{cccc}

\frac{r-l}{r-l+1} & \frac{1}{r-l+1}*x \\

1 & 0

\end{array}

\right| $ 即可。所有操作结束后，剩余的 $hvp_i$ 值就代表了“$i$ 从未被修改过，$A_i$ 从未改变的概率”，所以要记得给 $ans_i$ 在最后加上 $hvp_i*A_i$。

时间复杂度 $O(m$ $log n)$。

第二种：

基础思路：每次统计单个位置的答案；

仍然沿用第一种做法中将问题转化为矩阵乘法的想法，只是转化为每次统计单个位置答案；仍然倒转操作顺序，考虑对于一个 $i$，所有的操作 $j$ 分为两种：要么 $i\in[l_j,r_j]$，这种情况下 $i$ 对应的矩阵要乘上 $j$ 对应的矩阵；要么 $i\notin[l_j,r_j]$，这种情况下 $j$ 不对 $i$ 的矩阵产生影响；

由于每次的操作都在一个区间上进行，因此我们考虑差分；从左往右依次计算每个位置的答案，在左端点 $l_j$ 添加 $j$ 对当前位置答案的影响，在右端点 $r_j$ 时撤销这个影响，这样我们就能在 $O(n)$ 次影响的添加和撤销内，动态维护当前位置受到的所有影响。

具体实现上，可以仍然维护线段树，只是点数变成了 $m$ 个。添加操作 $j$ 对当前位置的影响时，我们将点 $j$ 上的矩阵修改为它的对应矩阵，撤销影响时则将其修改为单位矩阵；因为矩阵乘法没有交换律，所以在线段树的 $push_up$ 操作时要保证是左边的结果*右边的结果。

时间复杂度 $O(m$ $log m)$。