/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N,Q および A=(A_1,\ldots,A_N) が与えられます。
以下のクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。
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 を \bmod\ 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
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 x v
2 x
出力
クエリへの答えを改行区切りで出力せよ。
入力例 1
3 3 1 2 3 2 3 1 2 0 2 3
出力例 1
15 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 です。
入力例 2
2 1 998244353 998244353 2 1
出力例 2
0
Score : 500 points
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