Overview

This problem requires efficiently performing three operations on a queue: “append an element to the end,” “insert an element at a specified position,” and “delete the element at the front,” according to given queries.

Analysis

Naive Approaches and Their Limitations

Representative data structures for managing a queue include dynamic arrays (C++ std::vector or Python’s list) and linked lists (std::list). However, using these causes some operations to become bottlenecks, making it impossible to meet the time limit.

1. Using a dynamic array (std::vector, etc.)

   • Append to end (Operation 1): Can be done in \(O(1)\) time.
   • Insert at specified position (Operation 2) / Delete from front (Operation 3): All elements after the insertion/deletion point need to be shifted backward (or forward), which takes \(O(N)\) time in the worst case (\(N\) is the current length of the queue).
   • Overall complexity: With \(Q\) queries, the worst case is \(O(Q^2)\) time, which results in Time Limit Exceeded (TLE) under the constraint \(Q \le 2 \times 10^5\).

2. Using a doubly linked list (std::list, etc.)

   • Delete from front (Operation 3): Only requires rewriting the head pointer, so it can be done in \(O(1)\) time.
   • Insert at specified position (Operation 2): To locate the insertion position (the \(k\)-th element from the front), elements must be traversed sequentially from the head. This takes \(O(N)\) time in the worst case.
   • Overall complexity: Similarly, the worst case is \(O(Q^2)\) time, resulting in TLE.

Solution: Introducing a Balanced Binary Search Tree

To perform both “insertion at an arbitrary position” and “deletion from the front (a specific position)” efficiently, we need a self-balancing binary search tree that can manage array indices as keys. In particular, by using a data structure called an “Implicit Treap”, where each node stores “the size (number of elements) of the subtree rooted at itself,” we can determine positions without explicitly maintaining element indices, and all operations can be processed efficiently in \(O(\log N)\) time.

---

Algorithm

What is a Treap?

A Treap is a data structure that combines the properties of a Binary Search Tree (BST) and a Heap. Each node holds, in addition to its “value,” a randomly assigned “priority.” - BST property: The positional relationship with left and right children is maintained correctly. - Heap property: The priority of a parent node is always greater than or equal to (or less than or equal to) the priorities of its children.

By randomly determining priorities, the probability of the tree becoming skewed (degenerating into a linear chain) becomes extremely low, and the tree height is guaranteed to be \(O(\log N)\) on average.

Implicit Treap

A normal binary search tree orders elements by “key comparison,” but an Implicit Treap uses “the position from the left (index)” instead of keys. Each node \(t\) records the size cnt of the subtree rooted at itself.

\[\text{tree}[t].\text{cnt} = 1 + (\text{left child's cnt}) + (\text{right child's cnt})\]

By looking at the left child’s cnt, we can determine in \(O(1)\) that node \(t\) is at position “left_cnt-th from the left (0-indexed)” within its subtree.

Basic Operations: Split and Merge

The Implicit Treap is built using only the following two basic operations.

1. split(t, k, l, r) Splits tree t into tree l consisting of the first \(k\) elements, and tree r consisting of the remaining elements.
2. merge(t, l, r) Concatenates tree r after tree l, combining them into a single tree t. During this process, the parent-child priority relationship (heap property) is maintained.

Both operations execute in time proportional to the height of the tree, i.e., \(O(\log N)\) on average.

Processing Each Query

• Operation 1: 1 x (append \(x\) to the end)

  1. Create a new single-node tree \(u\) with value \(x\).
  2. Merge the current tree root with \(u\): merge(root, root, u).

• Operation 2: 2 x k (insert \(x\) at the \(k\)-th position from the front)

  1. Split the current tree root into the first \(k-1\) elements l and the remaining elements r: split(root, k - 1, l, r).
  2. Create a new single-node tree \(u\) with value \(x\).
  3. Merge \(u\) after l, then merge r after that to restore the tree: merge(l, l, u) \(\rightarrow\) merge(root, l, r).

• Operation 3: 3 (delete and output the front element)

  1. Split the current tree root into the first 1 element l and the remaining elements r: split(root, 1, l, r).
  2. Output the value stored in l.
  3. Set the new tree root to r (the front element l is removed from the tree).

---

Complexity

• Time complexity: Average \(O(Q \log Q)\) For each query (insertion, deletion, split, merge), Treap operations (split / merge) are performed in time proportional to the tree height. The maximum number of elements is \(Q\), and the tree height is maintained at \(O(\log Q)\) on average, so the overall time complexity is \(O(Q \log Q)\), which comfortably fits within the time limit.

• Space complexity: \(O(Q)\) The total number of nodes created throughout all queries is at most \(Q\). Since each node holds a constant number of integers, the space complexity is \(O(Q)\), which easily fits within the memory limit.

---

Implementation Notes

• Static array implementation without pointers: Dynamic memory allocation (such as the new operator) can be a cause of slow execution time. In this implementation, a struct array tree of size corresponding to the maximum number of queries (200005) is statically allocated in advance, and array indices are used as node IDs (instead of pointers) to achieve faster execution.

• Random number generator seed: std::mt19937 is used to randomly generate each node’s priority. This ensures that even against worst-case inputs intentionally designed to skew the tree, an expected height of \(O(\log N)\) is maintained.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.