問題
要素数 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』となる。
セグメントツリーを使って解くと幸せになれる。
入出力例を訂正しました。