C: Snuke and Spells - AtCoder Grand Contest 017
数列A[i]が与えられる。この数列は時刻tにX[i]番目がY[i]に変化する。時刻tでの数列に於いて、「k個の数がある時、kの数字を削除する」という操作を繰り返すことで数列を空にしたい。そのためには時刻tでの数列から何個の数字を変えればよいか。それぞれの時刻について答えよ。
数列内にYという数字が書かれた数がk個あるとき、[1, N]に対して [Y, Y - k) という被覆を考える。この被覆が[1, N]をダブりなくかつ完全に被覆するときに操作で空になることがわかる。すなわち、被覆されてない長さが変えなければいけない数字の個数である。
ここでX番目の数YがY'に変化すると被覆はそれぞれ
[Y, Y - k) -> [Y, Y - k + 1)
[Y', Y' - k') -> [Y', Y' - k' - 1)
という変化をする。まず初期状態の被覆について、それぞれの被覆の多重度をもつ配列count[y]を計算しておく。このcountを上の被覆の遷移に従って更新していく。この時、この変化によって元々被覆の多重度が0であったところが正になったり、その逆が起きた時全体の被覆されてない長さはそれぞれ1増えたり減ったりするのでそれをカウントしていくと、それぞれO(1)で計算できる。全体ではO(N+M)。
