No.1234 典型RMQ

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 188
作問者 :

koba-e964 / テスター :

紙ぺーぱー

1 ProblemId : 1379 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-08-16 18:22:40

問題文

配列に対して、
(1)区間に対する加算
(2)区間の最小値の計算
という２種類のクエリが複数与えられるので、それに答えてください。

入力

 $N$ 
 $a_{1}$   $a_{2}$   $\dots$   $a_{N}$ 
 $Q$ 
 $k_{1}$   $l_{1}$   $r_{1}$   $c_{1}$ 
 $k_{2}$   $l_{2}$   $r_{2}$   $c_{2}$ 
 $⋮$ 
 $k_{Q}$   $l_{Q}$   $r_{Q}$   $c_{Q}$

$1 \leq N, Q \leq 100000$
$- 10^{10} \leq a_{i} \leq 10^{10}$ for all $i$
$k_{i} = 1$ or $2$ for all $i$
$1 \leq l_{i} \leq r_{i} \leq N$ for all $i$
$- 10000 \leq c_{i} \leq 10000$ for all $i$
$N$ は与えられる配列の長さ、 $a_{1}, \dots, a_{N}$ は配列の初期値です。
$k_{i} = 1$ の場合、 $i$ 番目のクエリは「 $l_{i}$ 番目の要素から $r_{i}$ 番目の要素まで $c_{i}$ を加算して更新せよ」というクエリです。
$k_{i} = 2$ の場合、 $i$ 番目のクエリは「 $l_{i}$ 番目の要素から $r_{i}$ 番目の要素までの最小値を計算せよ」というクエリです。この場合 $c_{i}$ は無関係です。
初期値、およびクエリ処理後の配列の値が32bit整数の範囲に収まらない場合があることに注意してください。

出力

$k_{i} = 2$ であるようなクエリに対して、計算した最小値を1行に出力してください(各数値の出力後に改行してください)。

サンプル

サンプル1

入力

出力

1
3

初期値は{1,2,3,4}なので、1番目から4番目の要素の中の最小値は1です。 2番目のクエリで1番目から2番目まで3を加算して更新するので、配列の値は{4,5,3,4}になります。そのため3番目のクエリの出力は3です。

サンプル2

入力

7
-307365022 7783992359 -4511812607 6579404095 5544278142 -2979154502 -351466228
10
1 1 7 -744
2 2 2 0
1 1 7 6176
2 3 3 0
1 1 4 7390
2 6 6 0
2 6 6 0
2 5 5 0
1 3 5 5733
2 5 5 0

出力

7783991615
-4511807175
-2979149070
-2979149070
5544283574
5544289307

サンプル3

入力

16
-5636340242 558311214 179674564 -4196014631 4022013400 5437335202 -2472229134 8341925757 -4153003391 1020988529 4818814275 -1072289912 -3707805533 7612427682 -4413623203 -1139382259
10
1 14 14 -5404
2 12 15 0
1 4 15 1510
2 3 12 0
2 14 14 0
1 7 8 5589
1 10 15 3941
1 5 11 -5813
2 15 15 0
2 3 3 0

出力

-4413623203
-4196013121
7612423788
-4413617752
179674564

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。