配列の \(k\) 番目に挿入、末尾に挿入、先頭を出力し、先頭の要素を削除するといった操作を高速に行えることを求められています。

この配列を複数に分割し、配列の配列を管理することを考えます。各配列の長さが \(\mathrm{O}(\sqrt{Q})\) であるとします。このとき、配列の配列の長さも\(\mathrm{O}(\sqrt{Q})\) になります。このような手法を平方分割といいます。

実際にこの方法での各操作を行う方法を検討します。

• 末尾に挿入: 末尾の配列の末尾に要素を挿入する。もし、この挿入した配列が定数 \(B\) より大きくなる場合は配列を\(2\) 分割して配列の配列の末尾に置き換える。
• \(k\) 番目に挿入: \(k\) 番目の要素に相当する要素がどの配列にあるかを前から走査して特定する。特定した配列の該当する位置に挿入する。挿入した配列が定数 \(B\) より大きくなる場合は配列を\(2\) 分割して配列の配列の所定の位置に挿入。
• 先頭要素を出力し、先頭の要素を削除: 先頭の配列の先頭要素を参照する。出力したのちその要素を削除。先頭の配列が空になった場合は配列の配列からも先頭の配列自体を削除する。

この \(B\) を \(\mathrm{O}(\sqrt{Q})\) とすることで、すべての操作が\(\mathrm{O}(\sqrt{Q})\) 時間で行えるようになります。 このような配列の管理方法をC++では struct などで実装し、各配列はstd::deque を用いるとよいです。

C++ においては <ext/rope> を インクルードし、__gnu_cxx::rope を使うことで正解することは可能です。しかし、挿入の最悪計算量が長さを \(N\) とすると \(\mathrm{O}(N)\) となっていることに気を付ける必要があります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
static constexpr int BLOCK_SIZE = 500;
struct MyQueue {
    deque<deque<int>> blocks;
    MyQueue() {}
    void insert(int k, int v) {
        if (blocks.empty()) {
            blocks.emplace_back(deque<int>{v});
            return;
        }
        for (int i = 0; i < (int)blocks.size(); ++i) {
            if (k <= (int)blocks[i].size()) {
                blocks[i].insert(blocks[i].begin() + k, v);
                if (blocks[i].size() == 2 * BLOCK_SIZE) {
                    deque<int> ins(blocks[i].begin() + BLOCK_SIZE, blocks[i].end());
                    blocks.insert(blocks.begin() + (i + 1), ins);
                    blocks[i].resize(BLOCK_SIZE);
                }
                return;
            }
            k -= blocks[i].size();
        }
    }
    void push_back(int v) {
        if (blocks.empty()) {
            blocks.emplace_back(deque<int>{v});
            return;
        }
        blocks.back().emplace_back(v);
        if (blocks.back().size() == 2 * BLOCK_SIZE) {
            deque<int> l(blocks.back().begin(), blocks.back().begin() + BLOCK_SIZE);
            deque<int> r(blocks.back().begin() + BLOCK_SIZE, blocks.back().end());
            blocks.pop_back();
            blocks.emplace_back(l);
            blocks.emplace_back(r);
        }
    }
    int front() const {
        return blocks.front().front();
    }
    void pop_front() {
        blocks[0].pop_front();
        if (blocks[0].size() == 0) blocks.pop_front();
    }
};
int main() {
    MyQueue que;
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            que.push_back(x);
        } else if (t == 2) {
            int x, k;
            cin >> x >> k;
            k--;
            que.insert(k, x);
        } else if (t == 3) {
            cout << que.front() << endl;
            que.pop_front();
        }
    }
}