問題概要
相異なる $n$ 項からなる数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある．
次の 2 種からなるクエリを $q$ 個，順に処理せよ．
- $( 1, x, y )$ : $A$ に含まれる $x$ の直後に $y$ を挿入する（$x$ の存在は保証される）．
- $( 2, x )$ : $A$ に含まれる $x$ を削除する（$x$ の存在は保証される）．
各クエリの処理後，$A$ は空でなく，要素は相異なる．
最終的な $A$ を出力せよ．
制約
- $1 \leq n, q \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
解法
※実装が主題なので，C++ に寄った書き方になっています．他言語でも相当するライブラリをもっていると思うので，適宜読み替えてもらえると助かります．
やりたいこと自体は問題文そのままという感じがあります．とりあえず，各時点での $A$ を保持しながら実際に挿入・削除を行う方向で考えてみます．
前提として，$A$ の要素数の最大値が $\Theta( n + q )$ であることをリマークしておきます．
普段列を扱うときは（わたしは）専ら std::vector を使っているわけですが，std::vector では任意位置での挿入・削除の最悪計算量が $\Theta( n + q )$ 時間になるので，これを $\Theta( q )$ 回やってしまうと TLE します．よって，他の方法を考える必要があります．
競プロではやや影が薄い[要出典]ですが CS 分野では割と初期に習うデータ構造として，連結リストがあります．特に双方向リストは*1，対象の位置が分かっているとき，その位置での挿入・削除を $O( 1 )$ 時間で実行できます．わざわざ「対象の位置が分かっているとき」と言ったことから察せられるかもしれませんが，単純な実装では特定の要素の位置を知るのに最悪 $\Theta( n + q )$ 時間かかってしまいます．C++ では双方向リストは std::list として提供されていますが，要素の位置の特定に時間がかかるのは同様*2で，そのままでは使えません．逆に言えば，指定された要素の位置の特定さえ高速にできればよいので，この部分を別のデータ構造で補います．「要素から位置を知りたい」ということなので，単純に，要素毎にそれを保持するノードへのイテレータを保持する std::map を用意します．こうすれば，指定された要素のイテレータ（＝位置）を $O( \log( n + q ) )$ 時間で知ることができるようになります．位置さえ分かってしまえば挿入・削除は $O( 1 )$ 時間なので，これを $q$ 回やっても入力受け取りや初期化と合わせて $O( n + q \log( n + q ) )$ 時間となります．
コード
#include <list> int main() { IN( int, N ); VI A( N ); cin >> A; list< int > ls( ALL( A ) ); map< int, decltype( begin( ls ) ) > its; for ( auto it = begin( ls ); it != end( ls ); ++it ) { its[ *it ] = it; } IN( int, Q ); REP( Q ) { IN( int, T ); if ( T == 1 ) { IN( int, X, Y ); ls.insert( next( its[X] ), Y ); its[Y] = next( its[X] ); } else { IN( int, X ); ls.erase( its[X] ); } } VI res; copy( ALL( ls ), BI( res ) ); cout << res << endl; return 0; }
