005 - セグメントツリー技術基礎

時間制限 0.5 秒 / メモリ制限 64 MB / 得点 1 / x 2 /


TLE
0.5sec
MLE
64MB
得点
1

全員AC

問題

$0$から$n-1$番までの整数列がある。初期値は$0$である。
それについて以下の$Query$を処理せよ。

update pos value
数列の$pos$番目の値を$value$に変更する

add pos value
数列の$pos$番目の値に$value$を足す。

getMin begin end
数列で、区間$[begin, end)$の値の最小値を出力する。

getMax begin end
数列で、区間$[begin, end)$の値の最大値を出力する。

getSum begin end
数列で、区間$[begin, end)$の値の合計値を出力する。

入力

n m
Query1
...
Querym

出力

ans
Queryのget*が与えられるたびに出力する。

制約

$1$ ≤ $n$, $m$ ≤ $10$5
$0$ ≤ $pos$ ≤ $n$
$0$ ≤ $begin$ < $end$ ≤ $n$
$0$ ≤ $|value|$ ≤ $10000$

テストケース

例1

入力

10 10
getSum 0 10
update 0 10
getSum 0 10
add 0 10
getSum 0 10
add 0 -30
getSum 0 10
getMax 0 10
getMin 0 10
getSum 0 1

出力

0
10
20
-10
0
-10
-10