Range Arithmetic Query (hard)

2 secs 1024 MB
stoq's icon stoq

前書き

verify用の問題なのでTLが厳しめです。すみません。

問題文

長さ NN の数列 A1,,ANA_1,\dots,A_N があり、はじめ全ての要素は 00 です。

次の QQ 個のクエリを処理してください。

クエリ1

1 l r a b
  • Al,Al+1,,ArA_l, A_{l+1}, \dots, A_r をそれぞれ b, a+b, 2a+b, , (rl)a+bb,\ a+b,\ 2a+b,\ \dots,\ (r-l)a+b で更新する。

クエリ2

2 l r
  • Al,Al+1,,ArA_l, A_{l+1}, \dots, A_r の最小値を出力する。

クエリ3

3 l r
  • Al,Al+1,,ArA_l, A_{l+1}, \dots, A_r の最大値を出力する。

クエリ4

4 l r
  • Al,Al+1,,ArA_l, A_{l+1}, \dots, A_r の総和を出力する。

制約

  • 入力は全て整数

  • 1N2×1051 \leq N \leq 2 \times 10^5

  • 1Q2×1051 \leq Q \leq 2 \times 10^5

  • 1liriN1 \leq l_i \leq r_i \leq N (クエリ1, 2, 3, 4)

  • ai,bi105|a_i|,|b_i| \leq 10^5 (クエリ1)

入力

N Q
Query_1
...
Query_Q

出力

クエリ2, 3, 4の解を改行区切りで出力してください。

入力例1

10 20
4 8 10
3 6 10
4 3 10
1 1 10 9 -2
1 8 10 0 -8
4 3 5
3 1 9
4 6 10
4 4 6
3 2 7
3 9 10
3 1 6
2 1 5
1 5 6 6 5
1 4 8 10 4
3 7 8
2 7 10
4 2 2
1 7 8 7 -1
4 3 6

出力例1

0
0
0
75
52
71
102
52
-8
43
-2
44
-8
7
58

提出


Go (1.21)