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}

変色する日が早い順に並べると、次のようになる。

$0$ 日目では、各色の鳥の数は次のようになっている。

色の種類数は $6$ である。

$1$ 日目には、鳥 $4$ が色 $4$ から色 $6$ に変わる。

色4: 1 -> 0
種類数: 6 -> 5

色6: 1 -> 2
種類数: 5

処理後は次の状態になる。

各色の鳥の数: {1, 1, 1, 0, 1, 2}
種類数: 5

$2$ 日目に変色する鳥はいないので、状態は変わらない。

$3$ 日目には、鳥 $0$、鳥 $3$、鳥 $5$ が変色する。

鳥 $0$ は色 $1$ から色 $2$ に変わる。

色1: 1 -> 0
種類数: 5 -> 4

色2: 1 -> 2
種類数: 4

続いて、鳥 $3$ は色 $3$ から色 $5$ に変わる。

色3: 1 -> 0
種類数: 4 -> 3

色5: 1 -> 2
種類数: 3

鳥 $5$ は色 $6$ から色 $6$ に変わる。

色6: 2 -> 1 -> 2
種類数: 3

$3$ 日目の処理後は次の状態になる。

各色の鳥の数: {0, 2, 0, 0, 2, 2}
種類数: 3

残りの日も同様に処理すると、各日の処理後は次のようになる。

したがって、各日の答えは次のようになる。

5
5
3
3
4
4
4

注意点

特になし。

別解

特になし。