値が\(a_q\)である要素を愚直に移動することを考えます。このとき、\(a_q\)よりも後ろの\(P\)の要素をすべて1つ前にずらさないといけないため、\(1\)操作あたり最悪で\(\Theta(N)\)の計算量となって、合計の計算量が最悪\(\Theta(NQ)\)となり、TLEしてしまいます。 そこで、実際には要素を移動せず、その代わりにもともと\(a_q\)があった位置を\(-1\)に変更し、\(P\)の末尾に\(a_q\)を追加することを考えます。このとき、クエリごとに1要素の変更と1要素の末尾への追加をすることになり、どちらも償却\(O(1)\)時間で可能です。 \(1\leq i\leq N\)について、\(R_i=(P_j=iとなるj)\)となる数列\(R\)を考えることで、もともと\(a_q\)があった位置も\(O(1)\)時間で取得できます。要素を末尾に移動した際は\(R_{a_q} \leftarrow (Pの長さ)\)とすることで、\(R\)も\(O(1)\)時間で更新できます。 \(Q\)回の処理を終了した後、\(P\)から\(-1\)を除いた数列が答えの数列となっています。これより、この問題を\(O(N+Q)\)の計算量で解くことができました。 提出: https://atcoder.jp/contests/abc474/submissions/79033192