Sparse Table 練習問題 1 Erlang(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
説明
この章では Sparse Table の使い方を勉強します。
前の章では区間最小値を求めていましたが、Sparse Table では他の演算も行うことができます。
Sparse Table で行う演算は以下の 2 つの性質を満たす必要があります。
・結合則：演算の順序を入れ替えても結果が同じ
・冪等性：演算を何度行っても結果が同じ
例えば、min, max, gcd, bitwise AND, bitwise OR などはこれらの性質を満たします。
一方で、加算や乗算は冪等性を満たさないため Sparse Table では扱うことができません。
※補足：冪等性を満たす必要がある理由
Sparse Table では、区間 [l, r) の答えを求める際に区間 [l, l + 2^k) と [r - 2^k, r) の 2 つの部分区間に分割して答えを求めます。
このとき、区間 [r - 2^k, l + 2^k) は重複しているため、冪等性が成り立たない演算を扱うことができません。
例えば、加算では重複している区間を 2 回加算してしまうため、正しい答えを求めることができません。
問題
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・
l r：A_l, A_{l+1}, ..., A_{r-1} の bitwise OR を出力する。
- 入力される値
-
入力は以下のフォーマットで与えられます。
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
-
5 3
7 6 4 3 15
0 5
1 4
4 5
- 出力例1
-
15
7
15
- 入力例2
-
8 5
64 2 32 64 1 8 2 2
5 6
1 2
6 7
0 4
5 8
- 出力例2
-
8
2
2
98
10
- 入力例3
-
10 5
510226513 134221798 596184325 719355814 19904830 132894429 105966270 980564193 154177054 739648676
4 5
4 8
0 10
4 5
1 4
- 出力例3
-
19904830
1073741823
1073741823
19904830
736722919
