Sparse Table の構築 PHP編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
説明
前回の問題では、任意の長さの区間の最小値を 2 つの長さ 2^k の区間の最小値から求める方法を勉強しました。
各 i について i から始まる長さ 2^k の区間の最小値 T_{i,k} は愚直に計算していました。
しかし、愚直に計算していると数列の長さに対して 2 乗時間かかってしまうため、高速に計算したいです。
実は T_{i,k} も 2 つの 2 べきの長さの区間から求めることができます。
k > 0 のとき、T_{i,k} は以下の通りに長さ 2^{k-1} の 2 つの区間の答え T_{?,k-1} から求めることができます。
T_{i,k}
= min(A_i, A_{i+1}, ..., A_{i+2^{k-1}-1}, A_{i+2^{k-1}}, A_{i+2^{k-1}+1}, ..., A_{i+2^k-1})
= min(min(A_i, A_{i+1}, ..., A_{i+2^{k-1}-1}), min(A_{i+2^{k-1}}, A_{i+2^{k-1}+1}, ..., A_{i+2^k-1}))
= min(T_{i, k-1}, T_{i+2^{k-1}, k-1})
なお、いまは区間最小値を考えているため T_{i,0} = A_i です。
以上の方法で、すべての T_{i,k} を O(N log N) 時間で求めることができます（各 T_{i,k} の計算に O(1) 時間かかり、k は O(log N) 通り、i は O(N) 通りあるため）。
問題
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・
l r：数列 A の区間 [l,r) の最小値 min(A_l, A_{l+1}, ..., A_{r-1}) を出力する。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
l_1 r_1
l_2 r_2
...
l_Q r_Q
・1 行目には、数列の長さを表す整数 N とクエリの数を表す整数 Q が与えられます。
・2 行目には、数列 A が空白区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 10^5
・1 ≦ Q ≦ 10^5
・1 ≦ A_i ≦ 10^9
・0 ≦ l_i < r_i ≦ N
- 入力例1
-
8 4
11 4 8 9 17 15 1 15
2 3
0 6
7 8
0 8
- 出力例1
-
8
4
15
1
- 入力例2
-
8 8
561 873 601 189 469 314 234 970
2 8
2 6
5 6
2 3
0 3
3 7
1 2
0 8
- 出力例2
-
189
189
314
601
561
189
873
189
- 入力例3
-
10 10
712116246 506775207 260852535 867817625 201679930 942939639 944977915 665807832 603591403 570738402
2 4
0 1
2 6
6 10
8 9
8 9
2 3
1 3
3 4
1 10
- 出力例3
-
260852535
712116246
201679930
570738402
603591403
603591403
260852535
260852535
867817625
201679930
