競技プログラミング用 知識集積所
ABC420C - Sum of Min Query
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
愚直にやると、Q個のクエリ1回1回にN回の計算が必要になってTLE。
よって、高速化を考える。
よって、高速化を考える。
毎回の和を考えてみると、前回の和と1ヶ所以外内容が全く変わらない。
つまり、2回目以降は改めて和を取るのではなく、変更分の影響だけ考え直す方が速い。
つまり、2回目以降は改めて和を取るのではなく、変更分の影響だけ考え直す方が速い。
ということで、事前に全ての場所の小さい方の値を合計しておく。
その後クエリを受け取るごとに、まずx番目の影響を取り除いて、値の更新後、改めてx番目の影響を足しなおす、を繰り返せばよい。
その後クエリを受け取るごとに、まずx番目の影響を取り除いて、値の更新後、改めてx番目の影響を足しなおす、を繰り返せばよい。
解答例
注意点
答えがint型に入らない場合がある
巨大な数をずらっと並べられた場合に、和が2*10^9を超える場合がある。
long long型を使うこと。
long long型を使うこと。
