概要

病院の待ち行列を管理するシステムで、末尾への追加・任意位置への挿入・先頭からの取り出しの3種類の操作を効率的に処理する問題です。

考察

素朴なアプローチの問題点

Python のリストを使って素直に実装すると： - 末尾への追加: \(O(1)\) - 位置 \(k\) への挿入: \(O(N)\)（挿入位置以降の要素をずらす必要がある） - 先頭からの削除: \(O(N)\)（全要素を前にずらす必要がある）

\(Q\) が最大 \(2 \times 10^5\) なので、最悪ケースでは \(O(Q \times N) = O(Q^2)\) となり、TLE の恐れがあります。

解決のアイデア

平方分割（sqrt decomposition） を用いることで、各操作を \(O(\sqrt{Q})\) で処理できます。

待ち行列全体を複数の小さなブロック（リスト）に分割して管理します。各ブロックのサイズを \(O(\sqrt{Q})\) に保つことで、挿入・削除を高速に行えます。

アルゴリズム

平方分割による列の管理

待ち行列を「ブロックのリスト」として管理します。各ブロックは Python のリストです。

例: 待ち行列 [3, 1, 4, 1, 5, 9, 2, 6] をブロックサイズ3程度で分割すると：

blocks = [[3, 1, 4], [1, 5, 9], [2, 6]]

各操作の実装

1. 末尾追加 (1 x): 最後のブロックの末尾に追加。ブロックが大きくなりすぎたら分割。

2. 位置 \(k\) への挿入 (2 x k): 各ブロックのサイズを順に見て、挿入先のブロックを特定し、そのブロック内で insert を実行。ブロックが大きくなりすぎたら半分に分割。

3. 先頭の取り出し (3): 最初のブロックの先頭要素を pop(0) で取り出し。ブロックが空になったら削除。

具体例

操作: 1 5 → blocks = [[5]]
操作: 1 3 → blocks = [[5, 3]]
操作: 1 7 → blocks = [[5, 3, 7]]
操作: 2 9 2 → 位置2に9を挿入 → blocks = [[5, 9, 3, 7]]
操作: 3 → 先頭の5を出力 → blocks = [[9, 3, 7]]
操作: 3 → 先頭の9を出力 → blocks = [[3, 7]]

ブロックの分割

ブロックサイズが \(2 \times \text{BLOCK}\) を超えたとき、そのブロックを半分に分割します。これにより、各ブロックのサイズは常に \(O(\sqrt{Q})\) に保たれます。

計算量

• 時間計算量: \(O(Q\sqrt{Q})\)
  • 挿入先ブロックの探索: ブロック数 \(O(\sqrt{Q})\) 個を走査
  • ブロック内の挿入・削除: ブロックサイズ \(O(\sqrt{Q})\)
  • 各操作は \(O(\sqrt{Q})\)、全体で \(O(Q\sqrt{Q})\)
• 空間計算量: \(O(Q)\)（全要素を保持するため）

実装のポイント

• BLOCK サイズの設定: int(math.sqrt(Q * 2)) + 1 程度に設定。小さすぎるとブロック数が増えて走査コストが上がり、大きすぎるとブロック内操作のコストが上がるため、バランスが重要。

• 高速入出力: stdin.buffer.read() で一括読み込みし、出力も '\n'.join(out) でまとめて行うことで I/O のオーバーヘッドを削減。

• ブロックが空になるケースの処理: 先頭から取り出した後にブロックが空になったら、そのブロックをリストから削除する。

  ソースコード

import sys
from sys import stdin

class BIT:
    """Binary Indexed Tree for prefix sums, used to find k-th element."""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
    
    def find_kth(self, k):
        """Find the smallest index i such that prefix_sum(i) >= k."""
        pos = 0
        bit_mask = 1
        while bit_mask <= self.n:
            bit_mask <<= 1
        bit_mask >>= 1
        while bit_mask > 0:
            next_pos = pos + bit_mask
            if next_pos <= self.n and self.tree[next_pos] < k:
                k -= self.tree[next_pos]
                pos = next_pos
            bit_mask >>= 1
        return pos + 1


def main():
    input_data = stdin.buffer.read().split()
    idx = 0
    Q = int(input_data[idx]); idx += 1
    
    # We'll assign each inserted patient a unique slot index.
    # Total insertions <= Q, so we need at most Q slots.
    # We use a BIT of size Q to track which slots are occupied.
    # For insertion at position k (1-indexed in the queue), we need to find
    # the slot corresponding to the k-th occupied position, then insert just before it
    # (or at the end).
    
    # Actually, we need a data structure that supports:
    # 1. Insert at position k (1-indexed)
    # 2. Delete from position 1
    # 3. Get element at position 1
    
    # We'll use an order-statistic approach with a BIT.
    # Each element gets a unique "key" in [1, max_size].
    # We maintain a BIT where bit[i] = 1 if slot i is occupied.
    # To insert at position k, we need to find where to place it.
    
    # Strategy: use a large enough array. We interleave slots.
    # Actually, let's use a simpler approach: balanced BST via sorted list with BIT.
    
    # Approach: We have at most Q operations total, so at most Q elements ever inserted.
    # We assign "real positions" using a coordinate system. We'll use a BIT of size Q.
    # We maintain a mapping from slot -> patient_number.
    # For each insertion, we pick a new slot. But we need to insert at a specific position.
    
    # Let's use a different approach: we use a BIT to represent occupancy, and we 
    # assign slots from a pool. When inserting at position k, we find the k-th occupied 
    # slot... but we need to insert BEFORE it. So we need empty slots between occupied ones.
    
    # Better approach: Use a treap or skip list. But in Python, let's use the 
    # "sqrt decomposition" approach for an order-statistic list.
    
    import math
    
    BLOCK = max(1, int(math.sqrt(Q * 2)) + 1)
    blocks = []  # list of lists
    
    def _find(k):
        """Find block and index for the k-th element (0-indexed)."""
        for i, b in enumerate(blocks):
            if k < len(b):
                return i, k
            k -= len(b)
        return -1, -1
    
    def insert(k, val):
        """Insert val at 1-indexed position k."""
        k -= 1  # 0-indexed
        for i, b in enumerate(blocks):
            if k <= len(b):
                b.insert(k, val)
                if len(b) > 2 * BLOCK:
                    # split
                    mid = len(b) // 2
                    blocks.insert(i + 1, b[mid:])
                    blocks[i] = b[:mid]
                return
            k -= len(b)
        # append at end
        if not blocks:
            blocks.append([val])
        else:
            blocks[-1].append(val)
            if len(blocks[-1]) > 2 * BLOCK:
                b = blocks[-1]
                mid = len(b) // 2
                blocks[-1] = b[:mid]
                blocks.append(b[mid:])
    
    def pop_front():
        val = blocks[0].pop(0)
        if not blocks[0]:
            blocks.pop(0)
        return val
    
    out = []
    for _ in range(Q):
        op = int(input_data[idx]); idx += 1
        if op == 1:
            x = int(input_data[idx]); idx += 1
            # append to end
            if not blocks:
                blocks.append([x])
            else:
                blocks[-1].append(x)
                if len(blocks[-1]) > 2 * BLOCK:
                    b = blocks[-1]
                    mid = len(b) // 2
                    blocks[-1] = b[:mid]
                    blocks.append(b[mid:])
        elif op == 2:
            x = int(input_data[idx]); idx += 1
            k = int(input_data[idx]); idx += 1
            insert(k, x)
        else:
            out.append(str(pop_front()))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。