103325: [Atcoder]ABC332 F - Random Update Query
Description
Score : $550$ points
Problem Statement
You are given an integer sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
We will perform the following operation on $A$ for $i = 1, 2, \ldots, M$ in this order.
- First, choose an integer between $L_i$ and $R_i$, inclusive, uniformly at random and denote it as $p$.
- Then, change the value of $A_p$ to the integer $X_i$.
For the final sequence $A$ after the above procedure, print the expected value, modulo $998244353$, of $A_i$ for each $i = 1, 2, \ldots, N$.
How to print expected values modulo $998244353$
It can be proved that the expected values sought in this problem are always rational. Furthermore, the constraints of this problem guarantee that if each of those expected values is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$.
Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Report this $z$.
Constraints
- All input values are integers.
- $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$
Input
The input is given from Standard Input in the following format:
$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$
Output
Print the expected values $E_i$ of the final $A_i$ for $i = 1, 2, \ldots, N$ in the format below, separated by spaces.
$E_1$ $E_2$ $\ldots$ $E_N$
Sample Input 1
5 2 3 1 4 1 5 1 2 2 2 4 0
Sample Output 1
499122179 1 665496238 665496236 5
We start from the initial state $A = (3, 1, 4, 1, 5)$ and perform the following two operations.
- The first operation chooses $A_1$ or $A_2$ uniformly at random, and changes its value to $2$.
- Then, the second operation chooses one of $A_2, A_3, A_4$ uniformly at random, and changes its value to $0$.
As a result, the expected values of the elements in the final $A$ are $(E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5)$.
Sample Input 2
2 4 1 2 1 1 3 2 2 4 1 1 5 2 2 6
Sample Output 2
5 6
Sample Input 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
Sample Output 3
821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158
Input
Output
问题描述
给你一个长度为 $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$ 取模）。
如何对 $998244353$ 取模打印期望值
可以证明，本问题中寻求的期望值总是有理数。此外，本问题的约束条件保证了如果每个期望值表示为不可约分数 $\frac{y}{x}$，则 $x$ 不会被 $998244353$ 整除。
现在，存在一个唯一的整数 $z$，其范围在 $0$ 到 $998244352$（包含）之间，满足 $xz \equiv y \pmod{998244353}$。报告这个 $z$。
约束条件
- 所有的输入值都是整数。
- $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$
输入
输入从标准输入按以下格式给出：
$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
5 2 3 1 4 1 5 1 2 2 2 4 0
样例输出 1
499122179 1 665496238 665496236 5
我们从初始状态 $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)$。
样例输入 2
2 4 1 2 1 1 3 2 2 4 1 1 5 2 2 6
样例输出 2
5 6
样例输入 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