(問題 6)Segment Treeの更新2 : Segment Treeの更新 Ruby編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(はじめに)
問題 5 では親のインデックス計算方法についてやってきました。
その計算方法を用いて、Segment Treeの一点更新を行っていきましょう。
A の i 番目(0-indexed)の要素に対応する葉は頂点 N - 1 + i と計算できるので、問題 5 の T = N - 1 + i のケースと同様に更新対象の頂点を求めていき、葉に近い順(問題 5 での出力順)で計算を行いましょう。
(問題)
配列の長さが n である配列 A が与えられます。問題 3 の手順でSegment Treeを構築し、その配列を Tree とします。
Q 個のクエリが与えられるので順番に処理を行ってください。i 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
n Q
A_0 A_1 ... A_{n - 1}
p_1 x_1
p_2 x_2
...
p_Q x_Q
1 行目には 2 つの整数 n,Q が与えられます。
2 行目には n 個の整数 A_0,A_1,...,A_{n - 1} が与えられます。
2 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 p_i,x_i が与えられます。
入力は合計 2 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを Q 行で出力してください。
i (1 ≦ i ≦ Q) 行目には、i番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ n ≦ 256
- 1 ≦ Q ≦ 300
- 0 ≦ A_i ≦ 10 ^ 9 (0 ≦ i ≦ n - 1)
- 0 ≦ p_i ≦ n - 1 (1 ≦ i ≦ Q)
- 0 ≦ x_i ≦ 10 ^ 9 (1 ≦ i ≦ Q)
- 入力例1
-
5 2
1 5 7 9 8
3 6
0 5
- 出力例1
-
8 7 8 5 7 8 0 1 5 7 6 8 0 0 0
8 7 8 5 7 8 0 5 5 7 6 8 0 0 0
- 入力例2
-
1 3
100
0 90
0 80
0 70
- 出力例2
-
90
80
70
