Disjoint Sparse Table の構築 C編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
説明
前の問題で学んだ方法を用いて、Disjoint Sparse Table を構築します。
各レベルのすべての分割した区間に対して演算結果を前計算します（画像の黒の直線で示された区間）。
しかし、すべての区間に対して演算結果を愚直に計算すると計算時間が大きくなってしまいます。
そこで、各レベルの各分割境界 m を基点として、外側に向かって演算結果を計算していきます。
外側に向かう区間の演算結果は、演算結果の累積を用いることで高速に計算できます（「演算結果の累積」とは、例えば加算なら累積和のことを指します）。
画像は N = 8 の場合の例です。黒の直線が演算結果を計算すべき区間を表しています。レベル 2 の区間では、オレンジの矢印が示す向きに演算結果の累積を用いて計算します。
クエリに対する演算結果は、前の問題で学んだ方法で区間を分割することで O(1) 時間で計算できます。
なお、長さ 1 の区間は分割することができないため、例外処理が必要です。
問題
数列の長さ N が与えられます。
上記の方法で Disjoint Sparse Table を構築し、Q 個のクエリに答えてください。クエリの形式は以下の通りです。
・
l r：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^3
・0 ≦ l_i < r_i ≦ N
- 入力例1
-
10 3
712 245 304 185 51 353 711 193 531 159
2 10
3 7
9 10
- 出力例1
-
2487
1300
159
- 入力例2
-
16 5
430 684 167 312 126 10 946 780 292 589 410 146 527 578 231 445
5 7
0 7
15 16
10 11
8 9
- 出力例2
-
956
2675
445
410
292
- 入力例3
-
20 8
586 995 415 388 970 996 258 646 666 990 309 781 377 904 793 979 619 680 259 271
19 20
0 7
14 20
15 17
11 12
8 10
14 20
1 15
- 出力例3
-
271
4608
3601
1598
781
1656
3601
9488
