005 - セグメントツリー練習

問題

要素数 n の配列が与えられる。

その後、"update" , "min" , "exit" の各命令と、命令に応じた入力がされる。

update ... 配列の a 番地の値を、 b に変更する。

min ... 配列の a 番地から b までの値の最小値を出力する。

exit ... プログラムを終了する。

制約

nは2の累乗である。

n<=2^17

入出力形式

入力形式

n
a0 a1 ... an-1
.
.
.
exit

update
a b

min
a b

入出力例

入力例

8
4 7 2 9 1 5 7 1
min
0 7
min
0 3
update
2 5
min
0 3
exit

出力例

1
2
4

解説

0番地から7番地までの値の最小値は4番地と7番地の『1』である。

0番地から3番地までの値の最小値は2番地の『2』である。

2番地の値が『5』に変更される。

0番地から3番地までの値の最小値は0番地の『4』となる。

セグメントツリーを使って解くと幸せになれる。

入出力例を訂正しました。