ABC474 C - Remove and Append

考え方

並べなおすときには、その値は必ず最後に並ぶ。
ということは、「並べなおす」という行為を最後に行った人ほど後ろにある。
ならば、逆再生で解いていけば簡単である。

クエリを先に全て受け取り、これを逆から見る。
初めて見た値があれば、配列の最後尾から順に入れる。
その数を見たことがあるかを vector<bool> で管理するとよい。

クエリ分が終わったら、元の順列も見る。
これも、逆順に見て初めて見た値があれば、配列の最後尾から順に入れる。

この処理が終わったら、自然と最終状態の順列ができあがっている。
計算量は $O(N+Q)$ である。

入力例1での動作

入力を受け取る。

n: 4
q: 2
p: {2, 4, 3, 1}
a: {3, 2}

まずクエリを逆から見て、初めて見た値を最終状態の後ろから並べる。

これで、クエリによって並べなおされた値の位置が決まった。

次に、元の順列を逆から見る。
元の順列を逆から見ると、$1,3,4,2$ の順になる。
すでに並んでいる $2,3$ は飛ばし、初めて見る値だけを残りの位置へ後ろから入れる。

全ての位置が埋まり、最終状態は $4,1,3,2$ となる。

注意点

特になし。

別解

逆再生が思いつかなければ、各値が何番目にいるかを管理してシミュレーションしてもよい。
ただし、どれかが抜けたときに前に詰めるのは計算量が $O(NQ)$ になってしまう。

そこで、抜けたときはそこを空席にして、$N+1$ 番目以降に並ぶと考えることにする。
最終的に各値がいる位置を見て「位置、値」という pair を何らかの方法でソートすればよい。
こうすれば計算量は $O(N\log N+Q)$ で済む。