I hate Associative Property

2 secs 1024 MB
someone's icon someone

問題文

だれさんは結合法則が嫌いです。ある日、だれさんは次のような関数 ff を見つけました。

f(a,b)=a+b2 mod998244353f(a, b) = \frac{a + b}{2}\ \bmod 998244353\quad (a,bZ0)(a, b \in \mathbb{Z}_{\geq 0})

この関数は一般に f(f(a,b),c)f(a,f(b,c))f(f(a, b), c) \neq f(a, f(b, c)) となるので、結合法則を満たしません。 だれさんはこの関数を非常に気に入ったため、この関数を使って以下のような問題を考えました。解いてください。

長さ NN の整数列 A1,A2,,ANA_1, A_2, \ldots, A_N が与えられます。QQ 個のクエリが与えられるので処理してください。

  • 0 0\ i i\ xx\quad Ai=xA_i = x と変更する。
  • 1 1\ l l\ rr\quad f(f(f(Al,Al+1),Al+2),,Ar)f(\cdots f(f(A_l, A_{l+1}), A_{l+2}), \cdots, A_r) を出力する。

ただし  a+b2 mod998244353 \ \frac{a + b}{2}\ \bmod 998244353\  a+b2z mod998244353, 0z<998244353\ a + b \equiv 2z\ \bmod 998244353,\ 0\leq z\lt 998244353 を満たす唯一の整数 zz を表します。

入力

入力は以下の形式で与えられる。

N N\ QQ\\ A1 A_1\ A2 A_2\  \ldots\ ANA_N\\ Query\rm{Query} 1_1\\ Query\rm{Query} 2_2\\ \vdots\\ Query\rm{Query} Q_Q

各クエリは以下のいずれかの形式で与えられる。

type0

0 0\ i i\ x x\

type1

1 1\ l l\ r r\

制約

  • 2N2×1052\leq N\leq 2\times 10^5
  • 1Q2×1051\leq Q\leq 2\times 10^5
  • 0Ai<9982443530\leq A_i \lt 998244353
  • type0のクエリにおいて、1iN, 0x<9982443531\leq i\leq N,\ 0\leq x\lt 998244353
  • type1のクエリにおいて、1l<rN1\leq l\lt r\leq N (特に lrl\neq r であることに注意せよ。)

サンプル

サンプル1
4 3
4 8 4 4
1 2 3
0 1 8
1 1 4
出力1
6
5

クエリ 11 では 8+42=6\frac{8 + 4}{2} = 6 、クエリ 33 では 8+82+42+42=5\frac{\frac{\frac{8 + 8}{2} + 4}{2} + 4}{2} = 5 となります。

サンプル2
10 10
133403202 48156701 430605633 221185434 63259974 744846636 519917398 555439784 822174706 352853132
1 5 6
1 2 7
0 1 480330587
0 1 618069247
1 3 6
0 10 77287957
1 1 4
1 3 8
0 8 536865211
1 3 8
出力2
404053305
170911907
594492739
551083457
306761338
796596228

提出


Go (1.21)