No.1234 典型RMQ
タグ : / 解いたユーザー数 183
作問者 :
koba-e964
/ テスター :
紙ぺーぱー
問題文
配列に対して、
(1)区間に対する加算
(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もしくは右上の雲マークをクリックしてアカウントを作成してください。