Sparse Table 練習問題 4 Bash(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l d：max(A_l, A_{l+1}, ..., A_{r-1}) - min(A_l, A_{l+1}, ..., A_{r-1}) ≦ d を満たす最大の r を出力する。ただし、r は l < r ≦ N を満たすものとします。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
l_1 d_1
l_2 d_2
...
l_Q d_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 < N
・0 ≦ d_i ≦ 10^9
- 入力例1
-
10 10
17 19 15 6 14 5 10 7 13 17
2 8
0 19
3 4
4 10
2 9
6 6
0 2
4 2
9 0
2 18
- 出力例1
-
3
10
4
9
5
9
2
5
10
10
- 入力例2
-
10 10
1 5 5 7 7 8 11 12 14 20
8 31
8 36
8 598009261
5 12
8 18
0 2
8 1
1 14
2 12
5 154683365
- 出力例2
-
10
10
10
10
10
1
9
9
9
10
