ABC210 C Colorful Candies
この問題は, 差分更新をしていくことにより解くことができる. 具体的には, ある区間[
$ i, i + K
)から[
$ i + 1, i + 1 + K
)について, 区間内の色の種類数の変化については, mapとsetを併用することにより
$ O(\log N)
で求められる. よって考えられる区間を全探索することにより, この問題を
$ O(N \log N)
で解くことができた.
実装例:
https://atcoder.jp/contests/abc210/submissions/24284243