平方分割のまとめ CoffeeScript(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
整数 N, K と、 長さ N の配列 A = [A_1, A_2, ..., A_N] および K 個のクエリ Q が与えられます。
クエリは 以下の 3 種類存在し、 1 行に 1 つ与えられます。
- 0 L R: range_minクエリ。L 項目から R 項目までの中で最も小さい要素の値を出力する。
- 1 X Y: update_eachクエリ。X 番目の要素を Y で更新する。
- 2 L R D: update_rangeクエリ。L 項目から R 項目までの要素全てに D を加える。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N K
A_1
A_2
.
.
.
A_N
Q_1
Q_2
.
.
.
Q_K
* 1 行目では、配列 A の要素数 N および、クエリの個数 K が与えられます。
* 続く N 行では、配列 A の要素が先頭から順に与えられます。
* 続く K 行では、いずれかのクエリが 1 行に 1 つ与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
各range_maxクエリについて、配列 A の L 番目から R 番目までの要素のうち最小であるものの値を 1 行に 1 つ出力してください。
出力の最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
* 2 ≦ N ≦ 10000
* 1 ≦ K ≦ 10000
* 1 ≦ X ≦ N
* 1 ≦ L ＜ R ≦ N
* -100000 ≦ A_i, D, Y ≦ 100000
* 各クエリの終了時点で、配列 A の要素は常に -100000 ≦ A_i ≦ 100000 を満たすことが保証されます。
* 入力は合計で N + K + 1 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
- 入力例1
-
15 3
11193
-46904
94872
-40148
-19772
37429
-79883
75589
33480
-88935
33375
-49610
99981
12806
-6043
2 12 15 -21514
1 15 46564
0 9 15
- 出力例1
-
-88935
- 入力例2
-
30 4
-4340
94741
34270
-38004
59393
-1799
96751
70927
-79492
-60122
-86257
-48052
7491
-82475
-27391
74688
-83957
-34856
99615
-16351
80081
7425
-10751
43385
46702
24918
-51876
36594
-94640
65547
1 10 99459
0 21 25
2 2 26 -7402
0 9 13
- 出力例2
-
-10751
-93659
