Reverse Queue

この問題において、「$A$ を反転させる」というクエリを愚直に処理していては実行制限時間に間に合いません。

そこで、両端キュー (deque) というデータ構造を用いることによって「$A$ を反転させる」というクエリを疑似的に処理することができます。

両端キューは、先頭、最後尾に要素を追加、削除を $O(1)$ で行うことができます。

よって、$1, 2$ のクエリは以下のように言い換えることができます。

• 「$A$ を反転させる」クエリを奇数回処理したとき:

  1 x : $A$ の先頭に $x$ を追加する。
  2 : $A$ の最後の要素を出力する。その後、その要素を削除する。

• 「$A$ を反転させる」クエリを偶数回処理したとき:

  1 x : $A$ の最後尾に $x$ を追加する。
  2 : $A$ の最初の要素を出力する。その後、その要素を削除する。

結果として、この問題を $O(Q)$ で解くことができました。