ABC464 C - Plumage Palette

羽色パレット

考え方

まず、愚直解を考えてみる。
現在の各鳥の色を管理する配列を用意し、A の中身をコピーする。
$i$ 日目には、配列 D を見て鳥の色を書き換えてから、全体を見て各色の登場回数をカウンティング。
答えは、数えたカウンタの中の $1$ 以上になっている個数である。
しかしこの解法は、二重ループを回すため、計算量が $O(MN)$ となってしまい、TLE。

そこで、高速化を考える。
愚直解の中で無駄な部分を探すと、各色の登場回数をカウンティングの部分が見つかる。
どうせ毎回限られた数の鳥しか変色しないので、カウンティングの結果はほぼ前日と変わらない。
ならば、真面目に数えるのは $0$ 日目だけにし、以降は変化部分だけ修正していくことで高速化できる。

具体的には、以下のようになる。

まず、$2$ つの下準備をしておく。
$1$ つめ、配列 D を見て、変色が早い順にデータを取り出す準備をしておく。
これは、vector でソートするなり、priority_queue を用いるなり、どれでもよい。
$2$ つめ、$0$ 日目時点での各色の鳥の数をカウンティングし、何色いるかも取得する。
今の各鳥の色は、見ないので管理しない。

その後、$1$ 日ずつデータを処理する。
まず、下準備のデータを見て、その日に変色する鳥をすべて $1$ 羽ずつ処理する。
その鳥の色が $x$ から $y$ に変わるときには、以下の $2$ つの処理をする。

色 $x$ の鳥の数を $1$ 減らし、$0$ になった場合は種類数も $1$ 減らす。
色 $y$ の鳥の数を $1$ 増やす。増やす前に $0$ だった場合は種類数も $1$ 増やす。

その日の処理を終えた後の種類数が、その日の答えとなる。
更新は全日程合計で鳥の羽数しか行われないため、計算量は $O(N+M)$ または $O(N \log N+M)$ となり、間に合う。
（$\log N$ がつくかどうかは、イベントソートのやり方次第）

入力例1での動作

入力を受け取る。

n: 6
m: 7
a: {1, 2, 5, 3, 4, 6}
d: {3, 6, 5, 3, 1, 3}
b: {2, 5, 1, 5, 6, 6}

答え用の変数 result を用意する。

result: {0, 0, 0, 0, 0, 0, 0}

priority_queue に、色が変わる日と鳥の番号を入れておく。
（番兵として (m+1,-1) か何かを入れておいてもよい）
ここでは、データの入れ方の都合で、鳥番号は 0-indexed で扱っている。

que: {(1,4) | (3,0), (6,1), (5,2), (3,3), (3,5)}

初期状態では、各鳥の色は a に入っている色である。
そのため、各色の鳥の数 counters と、$1$ 羽以上いる色の種類数 kind は次のようになる。
counters.at(0) は、添字がずれないようにするダミーデータ。

a: {1, 2, 5, 3, 4, 6}
counters: {--, 1, 1, 1, 1, 1, 1}
kind: 6

$1$ 日目を処理する。
que の先頭は (1,4) なので、鳥 $4$ の色を $4$ から $6$ に変える。
色 $4$ の鳥がいなくなったので、kind を $-1$ する。

que: {(3,0) | (6,1), (5,2), (3,3), (3,5)}
counters: {--, 1, 1, 1, 0, 1, 2}
kind: 5
result: {5, 0, 0, 0, 0, 0, 0}

$2$ 日目を処理する。
que の先頭は (3,0) なので、$2$ 日目に色が変わる鳥はいない。

kind: 5
result: {5, 5, 0, 0, 0, 0, 0}

$3$ 日目を処理する。
que の先頭に日付が $3$ のものが $3$ つあるので、鳥 $0$、鳥 $3$、鳥 $5$ の色を変える。
その色の鳥がいなくなったり新しく現れたりしたら、kind も適切に処理する。

que: {(5,2) | (6,1)}
counters: {--, 0, 2, 0, 0, 2, 2}
kind: 3
result: {5, 5, 3, 0, 0, 0, 0}

$4$ 日目を処理する。
que の先頭は (5,2) なので、$4$ 日目に色が変わる鳥はいない。

que: {(5,2) | (6,1)}
kind: 3
result: {5, 5, 3, 3, 0, 0, 0}

$5$ 日目を処理する。
que の先頭は (5,2) なので、鳥 $2$ の色を 5 から 1 に変える。
色 $1$ の鳥が新しく現れたので、kind を $+1$ する。

que: {(6,1) | }
counters: {--, 1, 2, 0, 0, 1, 2}
kind: 4
result: {5, 5, 3, 3, 4, 0, 0}

$6$ 日目を処理する。
que の先頭は (6,1) なので、鳥 $1$ の色を 2 から 5 に変える。

que: {  }
counters: {--, 1, 1, 0, 0, 2, 2}
kind: 4
result: {5, 5, 3, 3, 4, 4, 0}

$7$ 日目を処理する。
que が空もしくは番兵なので、$7$ 日目に色が変わる鳥はいない。

que: {  }
kind: 4
result: {5, 5, 3, 3, 4, 4, 4}

注意点

特になし。

別解

特になし。