F - Two Sequence Queries Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。
Q 個のクエリが与えられるので、順に処理してください。

クエリは次の 3 種類です。

  • 1 l r x : A_l, A_{l+1}, \ldots, A_r に x を加える。
  • 2 l r x : B_l, B_{l+1}, \ldots, B_r に x を加える。
  • 3 l r : \displaystyle\sum_{i=l}^r (A_i\times B_i) を 998244353 で割った余りを出力する。

制約

  • 1\leq N,Q\leq 2\times 10^5
  • 0\leq A_i,B_i\leq 10^9
  • 1\leq l\leq r\leq N
  • 1\leq x\leq 10^9
  • 入力はすべて整数
  • 3 種類目のクエリが 1 つ以上存在する。

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{query}_i (1\leq i\leq Q) は i 番目に処理するクエリである。

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

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

1 l r x

2 l r x

3 l r

出力

3 種類目のクエリが K 個あるとき、K 行出力せよ。
i 行目 (1\leq i\leq K) には、i 個目の 3 種類目のクエリに対する出力を出力せよ。

入力例 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

出力例 1

16
25
84

最初、A=(1,3,5,6,8), B=(3,1,2,1,2) です。クエリは次の順で処理されます。

  • 1 個目のクエリでは (1\times 3)+(3\times 1)+(5\times 2)=16 を 998244353 で割った余りである 16 を出力します。
  • 2 個目のクエリでは A_2,A_3,A_4,A_5 に 3 を加えます。A=(1,6,8,9,11) となります。
  • 3 個目のクエリでは (1\times 3)+(6\times 1)+(8\times 2)=25 を 998244353 で割った余りである 25 を出力します。
  • 4 個目のクエリでは A_1,A_2,A_3 に 1 を加えます。A=(2,7,9,9,11) となります。
  • 5 個目のクエリでは B_5 に 2 を加えます。B=(3,1,2,1,4) となります。
  • 6 個目のクエリでは (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 を 998244353 で割った余りである 84 を出力します。

よって、1, 2, 3 行目にはそれぞれ 16, 25, 84 を出力します。

入力例 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

出力例 2

716070898
151723988

3 種類目のクエリでは 998244353 で割った余りを出力することに注意してください。

Score : 550 points

Problem Statement

You are given sequences of length N, A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You are also given Q queries to process in order.

There are three types of queries:

  • 1 l r x : Add x to each of A_l, A_{l+1}, \ldots, A_r.
  • 2 l r x : Add x to each of B_l, B_{l+1}, \ldots, B_r.
  • 3 l r : Print the remainder of \displaystyle\sum_{i=l}^r (A_i\times B_i) when divided by 998244353.

Constraints

  • 1\leq N,Q\leq 2\times 10^5
  • 0\leq A_i,B_i\leq 10^9
  • 1\leq l\leq r\leq N
  • 1\leq x\leq 10^9
  • All input values are integers.
  • There is at least one query of the third type.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i (1\leq i\leq Q) is the i-th query to be processed.

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 l r x

2 l r x

3 l r

Output

If there are K queries of the third type, print K lines.
The i-th line (1\leq i\leq K) should contain the output for the i-th query of the third type.

Sample Input 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

Sample Output 1

16
25
84

Initially, A=(1,3,5,6,8) and B=(3,1,2,1,2). The queries are processed in the following order:

  • For the first query, print (1\times 3)+(3\times 1)+(5\times 2)=16 modulo 998244353, which is 16.
  • For the second query, add 3 to A_2,A_3,A_4,A_5. Now A=(1,6,8,9,11).
  • For the third query, print (1\times 3)+(6\times 1)+(8\times 2)=25 modulo 998244353, which is 25.
  • For the fourth query, add 1 to A_1,A_2,A_3. Now A=(2,7,9,9,11).
  • For the fifth query, add 2 to B_5. Now B=(3,1,2,1,4).
  • For the sixth query, print (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 modulo 998244353, which is 84.

Thus, the first, second, and third lines should contain 16, 25, and 84, respectively.

Sample Input 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

Sample Output 2

716070898
151723988

Make sure to print the sum modulo 998244353 for the third type of query.