Overview

This problem requires efficiently performing “append to the end,” “insert at a specified position (cutting in line),” and “remove from the front (deletion)” operations on a queue of patients.

Since the number of elements in the queue can become large, directly using a regular array (list) will result in a Time Limit Exceeded (TLE). Therefore, we use a technique called “square root decomposition (bucket decomposition)” that divides the data into several chunks (blocks) to process all operations efficiently.

---

Analysis

Naive Approach and Its Limitations

Let’s consider simulating the operations directly using a regular Python list queue. - Operation 1 (append to end): queue.append(x) \(\rightarrow\) Fast at \(O(1)\) time. - Operation 2 (insert at specified position): queue.insert(k - 1, x) \(\rightarrow\) All elements after the insertion position need to be shifted back, so worst case \(O(N)\) time. - Operation 3 (remove from front): queue.pop(0) \(\rightarrow\) All remaining elements need to be shifted forward, so worst case \(O(N)\) time.

In the worst case, a single operation takes \(O(N)\) time. Since the number of queries \(Q\) is at most \(2 \times 10^5\), the overall computational complexity becomes \(O(Q^2)\) in the worst case, which will not fit within the time limit.

Optimization Idea: Square Root Decomposition

To reduce the cost of “shifting” elements, we divide the queue into several small blocks and manage them separately.

For example, when there are \(9\) elements in total, we divide them into \(3\) blocks of size \(3\). [1, 2, 3, 4, 5, 6, 7, 8, 9] \(\rightarrow\) [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

With this approach: 1. Locating a position: By summing up the number of elements in each block, we can quickly determine “which block and which position within that block” the \(k\)-th element is located at. 2. Insertion/Deletion: We perform insertion/deletion only within the identified single block. Since only the elements within that block (at most the block size) need to be shifted, this becomes very fast.

---

Algorithm

We set the maximum size of each block to approximately \(B \approx 1000\).

1. Data Management

• blocks: A 2D list storing the elements (patient numbers) of each block. Initial state is [[]].
• sizes: A list storing the number of elements in each block. Initial state is [0].

2. Operation 1: Append patient \(x\) to the end

1. Append \(x\) to the end of the last block blocks[-1], and increment sizes[-1] by \(1\).
2. If the size of the last block exceeds the limit (LIMIT = 1000), split the block in half.
   • Add the latter half of elements as a new block to the end of blocks and sizes.

3. Operation 2: Insert patient \(x\) at the \(k\)-th position from the front

1. Accumulate sizes from the beginning, and find the index idx of the first block where the cumulative sum reaches \(k\) or more.
2. Calculate the relative insertion position pos within that block.
3. Insert \(x\) at position pos in blocks[idx], and increment sizes[idx] by \(1\).
4. If the block size exceeds LIMIT after insertion, split the block in half.
   • Insert the latter half of elements as a new block at position idx + 1 (using insert).

4. Operation 3: Serve (delete) the patient at the front

1. Remove the first element from the front block blocks[0] using pop(0), store it in the output list, and decrement sizes[0] by \(1\).
2. If the front block becomes empty (sizes[0] == 0) and other blocks still exist, remove the empty front block from both blocks and sizes (using pop(0)).

---

Complexity

Let the maximum block size be \(B\) (in the implementation, \(B = 1000\)). If the total number of elements is \(N\) (at most \(Q\)), then the number of blocks is at most \(O(N/B)\).

• Time Complexity:

  • Operation 1: Appending to the end of a block is \(O(1)\). If a split occurs, it costs \(O(B)\).
  • Operation 2: Searching for the block to insert into takes \(O(N/B)\), insertion within the block takes \(O(B)\), and if a split occurs, it costs \(O(B)\). Therefore \(O(N/B + B)\).
  • Operation 3: Deletion from the front block is \(O(B)\). If the front block is removed, it costs \(O(N/B)\). Therefore \(O(N/B + B)\).
  • By setting \(B \approx \sqrt{Q}\), the worst-case complexity per query becomes \(O(\sqrt{Q})\).
  • The worst-case time complexity across all queries is \(O(Q \sqrt{Q})\). When \(Q = 2 \times 10^5\), combined with Python’s fast list operations, this comfortably fits within the time limit.

• Space Complexity:

  • Since the elements in the queue are distributed across blocks, it is \(O(Q)\).

---

Implementation Notes

• Block Splitting: If insertions are repeated, a specific block may become extremely long, making insertion/deletion within that block time-consuming. By splitting a block in half when its size exceeds LIMIT, we ensure that each block’s size remains at most \(O(B)\), guaranteeing the worst-case complexity.

• Fast I/O: Since we handle a large amount of input/output in Python, we use sys.stdin.readline and sys.stdout.write to prevent I/O from becoming a bottleneck.

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    Q = int(input())
    
    LIMIT = 1000
    blocks = [[]]
    sizes = [0]
    out = []
    
    for _ in range(Q):
        query = input().split()
        t = query[0]
        
        if t == '1':
            x = int(query[1])
            blocks[-1].append(x)
            sizes[-1] += 1
            if sizes[-1] > LIMIT:
                half = LIMIT // 2
                new_block = blocks[-1][half:]
                blocks[-1] = blocks[-1][:half]
                sizes[-1] = half
                blocks.append(new_block)
                sizes.append(len(new_block))
                
        elif t == '2':
            x = int(query[1])
            k = int(query[2]) - 1
            
            idx = 0
            curr_size = 0
            n_blocks = len(sizes)
            while idx < n_blocks:
                if curr_size + sizes[idx] >= k:
                    break
                curr_size += sizes[idx]
                idx += 1
            else:
                idx = n_blocks - 1
                curr_size -= sizes[-1]
                
            pos = k - curr_size
            blocks[idx].insert(pos, x)
            sizes[idx] += 1
            
            if sizes[idx] > LIMIT:
                half = LIMIT // 2
                new_block = blocks[idx][half:]
                blocks[idx] = blocks[idx][:half]
                sizes[idx] = half
                blocks.insert(idx + 1, new_block)
                sizes.insert(idx + 1, len(new_block))
                
        else:
            val = blocks[0].pop(0)
            sizes[0] -= 1
            if sizes[0] == 0 and len(sizes) > 1:
                blocks.pop(0)
                sizes.pop(0)
            out.append(str(val))
            
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

---

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