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$，打印每个 $i = 1, 2, \ldots, N$ 的 $A_i$ 的期望值，对 $998244353$ 取模。

输入格式

输入由标准输入按以下格式给出： $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$，以空格分隔，按 $i = 1, 2, \ldots, N$ 的顺序。 $E_1$ $E_2$ $\ldots$ $E_N$

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

499122179 1 665496238 665496236 5

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

5 6

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

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$我们从初始状态 $A = (3, 1, 4, 1, 5)$ 开始，执行下面两个操作。

第一次操作在 $A_1$ 和 $A_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)$.

标签: AtCoder|abc332F

来源

AtCoder|abc332F