ABC171 D - Replacing (400)
クエリ毎に和を毎回集計していると
$ O(NQ)
になる
クエリ毎に和の差分を求めることにする
事前に和とそれぞれの数字の登場回数を求めておく
和は
$ (C - B) \times Bの数
だけ増加
その後、Bの数を0にしてその分をCの数に加える
クエリ毎に
$ O(1)
になるので全体で
$ O(Q)
問題:
https://atcoder.jp/contests/abc171/tasks/abc171_d
提出:
https://atcoder.jp/contests/abc171/submissions/14547460
#ABC171
#400pt
#D
#ABC
#AtCoder
#O(Q)