\(A[i]=\) パーツ \(i\) が存在する座標

という配列のようなもので情報を持つことを考えます。クエリを処理するために必要な操作は

• 末尾の要素を取り除く
• 先頭に要素を追加する
• \(p\) 番目要素を答える

の \(3\) 種類です。これらの処理を配列に対して直接行うと「先頭に要素を追加する」に \(\Omega(N)\) 時間かかるため、実行時間制限に間に合わせることは極めて困難です。

C++ など、deque に対する添字アクセスが高速な言語では、deque を使うことで AC することができます。

実装例(C++)

Python など、deque に対する添字アクセスが高速でない言語では、配列をリバースし「先頭の要素を取り除く」処理を実際には行わないことで、すべての処理を高速に行うことができます。

実装例(Python)