Score : $500$ points

问题描述

给定 $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$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given $N$, $Q$, and $A=(A_1,\ldots,A_N)$.
Process $Q$ queries, each of which is of one of the following two kinds:

• 1 x v: update $A_x$ to $v$.
• 2 x: let $B_i=\sum_{j=1}^{i}A_j$, $C_i=\sum_{j=1}^{i}B_j$, and $D_i=\sum_{j=1}^{i}C_j$. Print $D_x$ modulo $998244353$.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format, where ${\rm query}_i$ denotes the $i$-th query to be processed:

$N$ $Q$

$A_1$ $A_2$ $\ldots$ $A_N$

${\rm query}_1$

${\rm query}_2$

$\vdots$

${\rm query}_Q$

Each query is given in one of the following two formats:

$1$ $x$ $v$

$2$ $x$

Output

Print the answer to the queries, with newlines in between.

Sample Input 1

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

Sample Output 1

15
9

When the $1$-st query is given, $A=(1,2,3)$, so $B=(1,3,6)$, $C=(1,4,10)$, and $D=(1,5,15)$; thus, $D_3=15$.

When the $3$-rd query is given, $A=(1,0,3)$, so $B=(1,1,4)$, $C=(1,2,6)$, and $D=(1,3,9)$; thus, $D_3=9$.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0

update @ 2024/3/10 10:54:10