AGC017 C. Snuke and Spells

問題

N個のボールが一列に並んでおり、各ボールには数字が書かれている。
魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。
例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,3}->3個あるので3が書かれたものが消える->{1}->1個あるので1が書かれたものが消える->{}となる。

各ボールは単位時間ごとに、ボール1個だけ数字が変化することがわかっており、変化する回数はM回であることもわかっている。
ここで、各単位時間ごとのボールの状態に対して、いくつか数字を書き換えて連続魔法で全消しができるようにする最小書き換え回数を求めたい。

制約

1 <= N,M <= 2*10^5
1 <= ボールの数字 <= N
1 <= 変化するボールの場所 <= N
1 <= 変化した後の数字 <= N

解法

まずは、あるボールの状態に対して、ボールの最小の書き換え回数を求める問題を考える。

魔法を発動するときのボールの位置は無関係なので、あるボールの状態をソートしたものを考える。
例えば、{1,3,3,5,5}のような場合、魔法を連続発動することで、全消しができる。
どういうときに全消しができるか考えると、

i 1 2 3 4 5
x 1 3 3 5 5

インデクスが5から5が2個、3から3が2個、1から1が1個、、、と、NからNがa個、N-aからN-aがb個、、、と続けられればよいことがわかる。
また、例えば、

i 1 2 3 4 5
x 1 3 3 4 4

の場合は、インデクスが5のとき値が4なので、全消しすることができないことがわかる。
たとえば、この4を5に書き換えると、インデクスが5から5が1個、4から4が1個、、、となり全消しができる。

ここで、全消しができる条件を考えると、各インデクスの部分について、ボールの数字で、すべてのインデクスをボールの数字の連続でカバーできるかどうか？になっている。(上だと、各数字のインデクスのところから各数字の連続ですべてのインデクスをカバーできている)

(難しいが)、これを扱うのに、数字aについて、[a-数字aの個数,a]という範囲を考える。
上の全消しができない場合の例{1,3,3,4,4}を考えると、カバーしている範囲の数を各インデクスで考えると、

i 1 2 3 4 5
r 1 1 2 1 0

のようになる。
5のときカバーできていないので、他の2以上になっているところから5のところに数字を書き換えてあげれば全面カバーができることがわかる。

ここで、書き換えてあげる必要がある数字の個数というのは、カバーされていないインデクス==0になっているところの数なので、これを求めてあげればよい。

数字が変化した場合は、各数字の個数から上のカバーしている範囲の数のところが1か所減って1か所増える、という変化を起こすので、各単位時間での変化はO(1)で更新できる。
前の状態で0の個数がわかっていればこの更新時に0になるかどうかみれば、こちらもO(1)で更新できる。