問題一覧 > 通常問題

No.1234 典型RMQ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 147
作問者 : koba-e964koba-e964 / テスター : 紙ぺーぱー紙ぺーぱー
1 ProblemId : 1379 / 出題時の順位表
問題文最終更新日: 2020-08-16 18:22:40

問題文

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

入力

$N$
$a_1$ $a_2$ $\ldots$ $a_N$
$Q$
$k_1$ $l_1$ $r_1$ $c_1$
$k_2$ $l_2$ $r_2$ $c_2$
$\vdots$
$k_Q$ $l_Q$ $r_Q$ $c_Q$

$1\le N,Q \le 100000$
$-10^{10} \le a_i \le 10^{10}$ for all $i$
$k_i = 1$ or $2$ for all $i$
$1 \le l_i \le r_i \le N$ for all $i$
$-10000 \le c_i \le 10000$ for all $i$
$N$は与えられる配列の長さ、$a_1, \cdots,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
入力
4
1 2 3 4
3
2 1 4 0
1 1 2 3
2 1 4 0
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。