Sparse Table の構築 Step 1 R(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
はじめに
この問題集では Sparse Table と呼ばれるデータ構造を学習します。
Sparse Table は静的な数列に対して適切な前計算を行うことで区間最小値などを高速に求めることができるデータ構造です。
Segment Tree などのように動的な更新には対応できませんが、クエリに対して定数時間で答えることができる点が特徴です。
また、2 次元への拡張や Disjoint Sparse Table など Sparse Table の応用についても扱います。
この問題集を順に学習していくことで、Sparse Table に関する知識を身につけ実装できるようになります。
問題
このセクションでは、Sparse Table の構築方法を学習し区間最小値を求めることを目指します。
まずは for 文などを用いて愚直に区間最小値を求めてみましょう。
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・
i k：数列 A の i から始まる長さ 2^k の区間の最小値 min(A_i, A_{i+1}, ..., A_{i+2^k-1}) を出力する。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
i_1 k_1
i_2 k_2
...
i_Q k_Q
・1 行目には、数列の長さを表す整数 N とクエリの数を表す整数 Q が与えられます。
・2 行目には、数列 A が空白区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 10^5
・1 ≦ Q ≦ 100
・1 ≦ A_i ≦ 10^9
・0 ≦ i_q ≦ N-1
・0 ≦ k_q
・i_q + 2^{k_q} ≦ N
- 入力例1
-
10 5
932677855 584814701 520826353 189926931 555327326 469526104 693813689 89379454 449888666 489015669
9 0
9 0
1 0
8 1
5 2
- 出力例1
-
489015669
489015669
584814701
449888666
89379454
- 入力例2
-
15 5
776196645 183708859 953209282 811268183 702007602 465314325 761607390 881357809 613505746 606836991 123985689 309869932 776500255 266980367 646812946
5 1
0 3
3 1
12 0
3 3
- 出力例2
-
465314325
183708859
702007602
776500255
123985689
- 入力例3
-
20 10
919188367 638474443 260473844 56312075 943068245 238951161 908148593 656133607 558069844 842292079 576983890 419311360 568102891 332673892 89360884 508562637 120938897 924935643 503162760 860404098
10 0
8 2
17 1
17 1
6 3
7 0
11 1
18 0
17 0
2 0
- 出力例3
-
576983890
419311360
503162760
503162760
332673892
656133607
419311360
503162760
924935643
260473844
