序列变换

算法思路

交换求和顺序，并利用相邻项抵消，可以得到

$$E=\sum_{j=1}^{n-1}b_{j} \left(\sum_{i=j}^{n-1}(a_{i}-a_{i+1})\right) =\sum_{j=1}^{n-1}b_{j}(a_{j}-a_{n}).$$

由于第 $n$ 项 $b_{n}(a_{n}-a_{n})=0$，可以将求和范围扩展到 $n$。

维护两个量

$$B=\sum_{i=1}^{n}b_{i},\qquad C=\sum_{i=1}^{n}a_{i} b_{i},$$

于是能量值可以写成

$$E=C-a_{n}B.$$

初始化时扫描两个序列，计算 $B$ 和 $C$。之后按以下方式处理事件：

• 修改 $a_{x}$：将 $C$ 增加 $v b_{x}$，再将 $a_{x}$ 增加 $v$。

• 修改 $b_{x}$：将 $C$ 增加 $v a_{x}$，将 $B$ 增加 $v$，再将 $b_{x}$ 增加 $v$。

• 查询：输出 $(C-a_{n}B+v)\bmod p$，其中 $p=998244353$。

所有数组元素和维护的总量都在模 $p$ 意义下保存。负数可通过 $(x\bmod p+p)\bmod p$ 转为非负余数，乘法使用 64 位整数。查询时始终使用当前的 $a_{n}$。

正确性证明

由上述求和变形，始终有 $E=C-a_{n}B$。

修改 $a_{x}$ 时，$C$ 中只有 $a_{x}b_{x}$ 一项发生变化，增量为 $vb_{x}$；修改 $b_{x}$ 时，$C$ 的增量为 $va_{x}$，$B$ 的增量为 $v$。因此，两类修改都能正确维护 $B$、$C$ 和数组的当前值。

查询时利用恒等式计算 $E+v$，并且取模与加减乘运算相容，所以算法输出正确。

复杂度分析

初始化需要 $O(n)$ 时间，每次修改和查询均为 $O(1)$，总时间复杂度为 $O(n+q)$。

保存两个序列需要 $O(n)$ 空间。