セグメント木を利用して \(O(Q\log Q)\) 時間で解けます。

操作 2 の \(k\) を適切に調整することで、以下の問題に言い換えられます。

• はじめ \(M=0\) である。操作を \(Q\) 回行う。
  • 操作 1：列の末尾に番号 \(x\) の人を追加する。
  • 操作 2：前から \(k\) 番目に番号 \(x\) の人を追加する。
  • 操作 3：\(M\) を \(1\) 増やす。
• すべての操作の後、前から \(M\) 人の番号を出力する。

最終的な列の並びを計算するためには操作列を後ろから見ればよいです。

• はじめに空きスペースを十分な個数（\(Q\) 個など）確保しておく。
• 操作 2 について、遅い順に「現在空いているスペースのうち前から \(k\) 番目の空きスペースに番号 \(x\) の人を入れる」を行う。
  • セグメント木上の二分探索を利用すれば一回あたり \(O(\log Q)\) 時間で計算できる。

実装例(C++)