(問題 9)Segment Treeの区間計算3 : 区間計算 Erlang(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(はじめに)
いよいよ、区間クエリに対する計算を行っていきましょう。
今回使っているmax演算には以下のような性質があります。
この性質により、Segment Treeで事前計算したものを用いて任意の区間に対して計算することが出来ます。
では、問題 8 で行った方法で区間分割をし、問題 7 の手法を用いて適切にSegment Treeからデータを取り出し、そのすべてのデータに対してmax演算を行って区間クエリを処理してみましょう。
(問題)
長さが n の配列 A が与えられます。Q 個のクエリが与えられるので順番に処理を行ってください。i 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
n
A_0 A_1 ... A_{n - 1}
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q
1 行目には 1 つの整数 n が与えられます。
2 行目には n 個の整数 A_0,A_1,...,A{n - 1} が与えられます。
3 行目には 1 つの整数 Q が与えられます。
3 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 L_i,R_i が与えられます。
入力は合計 3 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを Q 行で出力してください。
i (1 ≦ i ≦ Q) 行目には i 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ n ≦ 100000
- 0 ≦ A_i ≦ 10 ^ 9 (0 ≦ i ≦ n - 1)
- 1 ≦ Q ≦ 100000
- 0 ≦ L_i ≦ R_i ≦ n - 1 (1 ≦ i ≦ Q)
- 入力例1
-
5
1 5 7 9 8
15
0 0
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
- 出力例1
-
1
5
7
9
9
5
7
9
9
7
9
9
9
9
8
- 入力例2
-
1
1
1
0 0
- 出力例2
-
1
