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

输入 #1

5 2
3 1 4 1 5
1 2 2
2 4 0

输出 #1

499122179 1 665496238 665496236 5

输入输出样例 #2

输入 #2

2 4
1 2
1 1 3
2 2 4
1 1 5
2 2 6

输出 #2

5 6

输入输出样例 #3

输入 #3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

输出 #3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158

说明/提示

约束

• 输入的所有数均为整数。
• $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 翻译