第三回 アルゴリズム実技検定 K - コンテナの移動
愚直に実装するとクエリ毎にコンテナの位置を見つけて移動するので$ O(NQ)かかる
コンテナの発見と移動の計算量を削減したい
良いデータ構造が思い浮かばなかったので双方向リストで実装した
コンテナ番号と前後のポインタを持つ
それぞれの机の最後のポインタを持つ配列とそれぞれのコンテナのポインタを持つ配列を用意しておく
両方ともi番目の要素の最初の値はi番目のコンテナのポインタ
コンテナを移動する場合は、以下の要素を更新する
自身の前を指すポインタ
移動前の自身の前のコンテナの次の要素を示すポインタ
移動後の自身の前のコンテナの次の要素を示すポインタ
移動前後の机の最後のポインタ
最後にそれぞれの机の最後のポインタから前に見ていって存在する机を配列に格納し、0番から順に出力する
初期化と最後の位置の格納が$ O(N)、クエリ処理が$ O(1)で全体で$ O(N+Q)