概要

この問題は、待ち行列に対して「末尾への要素追加」「指定位置への要素挿入」「先頭の要素の削除」という3つの操作を、与えられたクエリに従って高速に行う問題です。

考察

素朴なアプローチとその限界

待ち行列を管理する代表的なデータ構造として、動的配列（C++の std::vector や Pythonの list）や連結リスト（std::list）が挙げられます。しかし、これらを使用すると一部の操作がボトルネックとなり、実行時間制限に間に合いません。

1. 動的配列（std::vector など）を用いる場合

   • 末尾への追加（操作1）: \(O(1)\) 時間で可能です。
   • 指定位置への挿入（操作2）/ 先頭の削除（操作3）: 挿入・削除した位置より後ろにあるすべての要素を後ろ（または前）にずらす必要があるため、最悪 \(O(N)\) 時間（\(N\) は現在の行列の長さ）かかります。
   • 全体での計算量: クエリ数を \(Q\) とすると、最悪で \(O(Q^2)\) 時間となり、 \(Q \le 2 \times 10^5\) の制約下では実行時間制限超過（TLE）になります。

2. 双方向連結リスト（std::list など）を用いる場合

   • 先頭の削除（操作3）: 先頭のポインタを書き換えるだけなので \(O(1)\) 時間で可能です。
   • 指定位置への挿入（操作2）: 挿入する位置（先頭から \(k\) 番目）を特定するために、先頭から順に要素を辿る必要があります。これに最悪 \(O(N)\) 時間かかります。
   • 全体での計算量: 同様に最悪 \(O(Q^2)\) 時間となり、TLE になります。

解決策：平衡二分探索木の導入

「任意の位置への挿入」と「先頭（特定位置）の削除」をともに高速に行うためには、配列のインデックスをキーとして管理できる平衡二分探索木（Self-balancing binary search tree）が必要です。 特に、各ノードに「自身を根とする部分木のサイズ（要素数）」を持たせることで、要素のインデックスを明示的に保持しなくても位置を特定できる「暗黙のTreap (Implicit Treap)」というデータ構造を使用すると、すべての操作を \(O(\log N)\) 時間で効率的に処理できます。

---

アルゴリズム

Treap（トリープ）とは

Treapは、二分探索木（Binary Search Tree）とヒープ（Heap）の特性を併せ持つデータ構造です。 各ノードには、保持する「値」のほかに、ランダムに割り当てられた「優先度（priority）」を持たせます。 - 二分探索木の性質: 左右の子との位置関係を正しく保ちます。 - ヒープの性質: 親ノードの優先度は、常に子ノードの優先度以上（または以下）になります。

優先度をランダムに決定することで、木が偏る（一列に並んでしまう）確率が極めて低くなり、木の高さが平均して \(O(\log N)\) に保たれることが保証されます。

暗黙のTreap (Implicit Treap)

通常の二分探索木は「キーの大小関係」で要素を並べますが、暗黙のTreapでは「左から何番目にあるか」という位置（インデックス）をキーの代わりに使います。 各ノード \(t\) に、自身を根とする部分木のサイズ cnt を記録しておきます。

\[\text{tree}[t].\text{cnt} = 1 + (\text{左の子のcnt}) + (\text{右の子のcnt})\]

これにより、左の子の cnt を見ることで、ノード \(t\) がその部分木の中で「左から何番目（0始まりで left_cnt 番目）」にあるかが \(O(1)\) で分かります。

基本操作：Split と Merge

暗黙のTreapは、以下の2つの基本操作だけで構築されます。

1. split(t, k, l, r) 木 t を、先頭から \(k\) 個の要素からなる木 l と、残りの要素からなる木 r の2つに分割します。
2. merge(t, l, r) 木 l の後ろに木 r を連結し、1つの木 t にまとめます。この際、優先度の親子関係（ヒープの性質）が保たれるように結合します。

これら2つの操作は、木の高さに比例する時間、すなわち平均 \(O(\log N)\) で実行できます。

各クエリの処理方法

• 操作1 : 1 x（末尾に \(x\) を追加）

  1. 値 \(x\) を持つ新しい1ノードの木 \(u\) を作成します。
  2. 現在の木 root と \(u\) を結合します：merge(root, root, u)。

• 操作2 : 2 x k（先頭から \(k\) 番目に \(x\) を挿入）

  1. 現在の木 root を、先頭から \(k-1\) 個の要素 l と、残りの要素 r に分割します：split(root, k - 1, l, r)。
  2. 値 \(x\) を持つ新しい1ノードの木 \(u\) を作成します。
  3. l の後ろに \(u\) を結合し、さらにその後に r を結合して元に戻します：merge(l, l, u) \(\rightarrow\) merge(root, l, r)。

• 操作3 : 3（先頭を削除して出力）

  1. 現在の木 root を、先頭の1個の要素 l と、残りの要素 r に分割します：split(root, 1, l, r)。
  2. l に格納されている値を出力します。
  3. 新しい木の根を r とします（先頭要素 l は木から取り除かれます）。

---

計算量

• 時間計算量: 平均 \(O(Q \log Q)\) 各クエリ（挿入・削除・分割・結合）において、Treapの操作（split / merge）は木の高さに比例する時間で行われます。要素数の最大値は \(Q\) であり、木の高さは平均して \(O(\log Q)\) に保たれるため、全体の時間計算量は \(O(Q \log Q)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(Q)\) クエリを通じて作成されるノードの総数は最大でも \(Q\) 個です。各ノードが保持する情報は定数個の整数であるため、空間計算量は \(O(Q)\) となり、メモリ制限にも十分収まります。

---

実装のポイント

• ポインタを使わない静的配列による実装: 動的なメモリ確保（new 演算子など）は実行時間がかかる原因になります。この実装では、あらかじめ最大クエリ数に対応するサイズ（200005）の構造体配列 tree を静的に確保し、配列のインデックスをノードのID（ポインタの代わり）として扱うことで高速化を図っています。

• 乱数生成器のシード値: std::mt19937 を用いて、各ノードの優先度（priority）をランダムに生成しています。これにより、意図的に木を偏らせるような最悪ケースの入力に対しても、期待値 \(O(\log N)\) の高さを維持することができます。

  ソースコード

#include <iostream>
#include <random>
#include <chrono>

using namespace std;

struct Node {
    int val;
    unsigned int priority;
    int cnt;
    int l, r;
};

Node tree[200005];
int node_cnt = 0;

int new_node(int val) {
    node_cnt++;
    tree[node_cnt].val = val;
    static mt19937 rng(1337);
    tree[node_cnt].priority = rng();
    tree[node_cnt].cnt = 1;
    tree[node_cnt].l = 0;
    tree[node_cnt].r = 0;
    return node_cnt;
}

int get_cnt(int t) {
    return t ? tree[t].cnt : 0;
}

void update(int t) {
    if (t) {
        tree[t].cnt = 1 + get_cnt(tree[t].l) + get_cnt(tree[t].r);
    }
}

void split(int t, int k, int &l, int &r) {
    if (!t) {
        l = r = 0;
    } else {
        int left_cnt = get_cnt(tree[t].l);
        if (k <= left_cnt) {
            split(tree[t].l, k, l, tree[t].l);
            r = t;
            update(r);
        } else {
            split(tree[t].r, k - left_cnt - 1, tree[t].r, r);
            l = t;
            update(l);
        }
    }
}

void merge(int &t, int l, int r) {
    if (!l || !r) {
        t = l ? l : r;
    } else if (tree[l].priority > tree[r].priority) {
        merge(tree[l].r, tree[l].r, r);
        t = l;
        update(t);
    } else {
        merge(tree[r].l, l, tree[r].l);
        t = r;
        update(t);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    if (!(cin >> q)) return 0;

    int root = 0;

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            int u = new_node(x);
            merge(root, root, u);
        } else if (type == 2) {
            int x, k;
            cin >> x >> k;
            int l, r;
            split(root, k - 1, l, r);
            int u = new_node(x);
            merge(l, l, u);
            merge(root, l, r);
        } else if (type == 3) {
            int l, r;
            split(root, 1, l, r);
            cout << tree[l].val << "\n";
            root = r;
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。