← 返回题目列表

AtCoder · abc332_f

I. 随机更新查询

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N.

我们将执行以下操作 A 为 i = 1, 2, \ldots, M 按此顺序。

  • 首先,选择一个整数 L_i 和 R_i,包含在内,均匀随机,表示为 p.
  • 然后,更改值 A_p 为整数 X_i.

对于最终序列 A 经过上述过程后,打印期望值,模 998244353,属于 A_i 对于每个 i = 1, 2, \ldots, N.

如何打印期望值模 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

输出

打印预期值 E_i 决赛 A_i 为 i = 1, 2, \ldots, N 格式如下,以空格分隔。

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 or 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