Cumulative Cumulative Cumulative Sum

题目描述

你被给定 $N$、$Q$ 和 $A=(A_1,\ldots,A_N)$。
处理 $Q$ 个查询，每个查询为以下两种类型之一：

$1 x v$：将 $A_x$ 更新为 $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$。

输入格式

输入按照下列格式从标准输入给出，其中 ${\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$

输出格式

按顺序输出各查询的答案，每个答案占一行。

3 3
1 2 3
2 3
1 2 0
2 3

15
9

2 1
998244353 998244353
2 1

0

提示

$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$ 输入中的所有数值均为整数。当给出第 $1$ 个查询时，$A=(1,2,3)$，所以 $B=(1,3,6)$，$C=(1,4,10)$，且 $D=(1,5,15)$；因此，$D_3=15$。 当给出第 $3$ 个查询时，$A=(1,0,3)$，所以 $B=(1,1,4)$，$C=(1,2,6)$，且 $D=(1,3,9)$；因此，$D_3=9$。

标签: AtCoder|abc256F

来源

AtCoder|abc256F