分数: 500 点
问题陈述
你被给予 N, Q,和 A=(A_1,\ldots,A_N).
流程 Q 查询,每个查询属于以下两种类型之一:
1 x v:更新 A_x to v.2 x:让 B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j,和 D_i=\sum_{j=1}^{i}C_j。 打印 D_x 模数 998244353.
约束
- 1 \leq N \leq 2\times10^5
- 1 \leq Q \leq 2\times10^5
- 0 \leq A_i \leq 10^9
- 1 \leq x \leq N
- 0 \leq v \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出,其中 {\rm query}_i 表示 i要处理的第一个查询:
N Q
A_1 A_2 \ldots A_N
{\rm query}_1
{\rm query}_2
\vdots
{\rm query}_Q
每个查询均以以下两种格式之一给出:
1 x v
2 x
输出
打印查询的答案,中间有换行符。
示例输入 1
3 3 1 2 3 2 3 1 2 0 2 3
示例输出 1
15 9
当 1-st 查询已给出, A=(1,2,3),所以 应打印 B=(1,3,6), C=(1,4,10),和 D=(1,5,15);因此, D_3=15.
当 3-rd 查询已给出, A=(1,0,3),所以 应打印 B=(1,1,4), C=(1,2,6),和 D=(1,3,9);因此, D_3=9.
示例输入 2
2 1 998244353 998244353 2 1
示例输出 2
0