Building Blocks

解説

配列の反転操作とpop操作が混在するため、データ構造を工夫する必要があります。ここでは、dequeとよばれるスタックとキュー構造を組み合わせた構造を用いると容易にクエリ処理を実装することができます。それぞれのクエリに対応する操作は以下の通りです。(bool型の変数flagを用意しておきます。最初はflag=Falseです。)

• クエリ$1$ : flagがFalseのとき配列の右側から、Trueのとき配列の左側から $k$ を配列に追加する。
• クエリ$2$ : flagがFalseのとき配列の左側から、Trueのとき配列の右側から $p$ 番目の積み木に書かれた数字を出力する。
• クエリ$3$ : flagがFalseのとき配列の一番右側、Trueのとき配列の一番左側の要素を取り除き、その数字を出力する。
• クエリ$4$ : flagのTrueとFalseを入れ替える。

時間計算量は適切にクエリ処理を行うことで$O(Q)$となり、今回の制約においては実行時間制限に十分間に合います。 よって、この問題を解くことができました。