AT_abc332_f [ABC332F] Random Update Query

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。 对于 $A$，依次进行 $i = 1, 2, \ldots, M$ 的如下操作： - 首先，从 $L_i$ 到 $R_i$ 之间的整数中等概率随机选取一个，记为 $p$。 - 然后，将 $A_p$ 的值修改为整数 $X_i$。 经过上述所有操作后，请输出最终 $A$ 中每个 $A_i$ 的期望值 $\bmod\ 998244353$，对于每个 $i = 1, 2, \ldots, N$。 期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数。并且，在本题的约束下，若将期望值表示为最简分数 $\frac{y}{x}$，则 $x$ 一定不会被 $998244353$ 整除。 此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入以如下格式从标准输入读入。 > $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $L_1$ $R_1$ $X_1$ $L_2$ $R_2$ $X_2$ $\vdots$ $L_M$ $R_M$ $X_M$

请输出最终每个 $A_i$ 的期望值 $E_i$，按照如下格式以空格分隔输出。 > $E_1$ $E_2$ $\ldots$ $E_N$

### 约束 - 输入的所有数均为整数。 - $1 \leq N, M \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ - $1 \leq L_i \leq R_i \leq N$ - $0 \leq X_i \leq 10^9$ ### 样例解释 1 初始状态为 $A = (3, 1, 4, 1, 5)$，进行如下两次操作： - 首先，第 1 次操作中，$A_1$ 和 $A_2$ 中的一个会被等概率选中，其值被改为 $2$。 - 然后，第 2 次操作中，$A_2, A_3, A_4$ 中的一个会被等概率选中，其值被改为 $0$。 最终，$A$ 的每个元素的期望值为 $(E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5)$。 由 ChatGPT 4.1 翻译