Day 077-Q1 | Double-Ended Priority Queue（MinMaxHeap）

問題

$N$ 個の整数列 $A_1, A_2, \ldots, A_N$ と $Q$ 個のクエリが与えられる。以下の操作を処理せよ。

クエリ 1: 1 x — 値 $x$ を集合に追加する
クエリ 2: 2 — 集合の最小値を出力し、集合から削除する
クエリ 3: 3 — 集合の最大値を出力し、集合から削除する
クエリ 4: 4 k — 集合の小さい方から $k$ 番目の値を出力する（削除しない）

初期状態は $A_1, \ldots, A_N$ を集合として持つ。

制約

パラメータ	範囲	備考
$N$	$1 \le N \le 2 \times 10^5$	初期要素数
$Q$	$1 \le Q \le 2 \times 10^5$	クエリ数
$A_i, x$	$1 \le A_i, x \le 10^9$	要素の値
クエリ 4 の $k$	$1 \le k \le$ 現在の集合サイズ	常に有効範囲内

入出力例

入力例1

出力例1

初期集合 {1,1,3,4,5}。最小=1削除→{1,3,4,5}。最大=5削除→{1,3,4}。2追加→{1,2,3,4}。2番目=2。9追加→{1,2,3,4,9}。最大=9削除。

概念図: BIT による順序統計木

BIT のインデックス $i$ に「値 $i$ の要素数」を保持。$k$ 番目は BIT 上の二分探索で $O(\log M)$。最小値 = $k=1$、最大値 = $k=\text{size}$ として統一処理。

ヒント

ヒント1（方向性）

最小値・最大値の両方を $O(\log N)$ で取り出せるデータ構造が必要。通常の min-heap は最小値のみ、max-heap は最大値のみ。両方を同時に管理するには工夫が必要。

ヒント2（アプローチ）

BIT + 座標圧縮による順序統計木: 値域を圧縮して BIT のインデックスにマッピング。各インデックスに「その値の要素数」を保持。最小値 = find_kth(1)、最大値 = find_kth(size) で統一的に処理できる。

ヒント3（ほぼ答え）

def find_kth(k):
    pos = 0
    log = M.bit_length()
    for i in range(log, -1, -1):
        nxt = pos + (1 << i)
        if nxt <= M and bit[nxt] < k:
            pos = nxt
            k -= bit[pos]
    return sorted_vals[pos]  # 0-indexed

模範解答

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    queries = []
    vals = list(A)
    for _ in range(Q):
        line = list(map(int, input().split()))
        queries.append(line)
        if line[0] == 1:
            vals.append(line[1])

    # 座標圧縮
    sorted_vals = sorted(set(vals))
    compress = {v: i+1 for i, v in enumerate(sorted_vals)}
    M = len(sorted_vals)

    # BIT（Fenwick Tree）
    bit = [0] * (M + 1)
    size = [0]

    def bit_update(i, d):
        while i <= M:
            bit[i] += d
            i += i & (-i)

    def find_kth(k):
        pos = 0
        log = M.bit_length()
        for i in range(log, -1, -1):
            nxt = pos + (1 << i)
            if nxt <= M and bit[nxt] < k:
                pos = nxt
                k -= bit[pos]
        return sorted_vals[pos]

    for a in A:
        bit_update(compress[a], 1)
        size[0] += 1

    out = []
    for q in queries:
        if q[0] == 1:
            x = q[1]
            bit_update(compress[x], 1)
            size[0] += 1
        elif q[0] == 2:
            v = find_kth(1)
            out.append(v)
            bit_update(compress[v], -1)
            size[0] -= 1
        elif q[0] == 3:
            v = find_kth(size[0])
            out.append(v)
            bit_update(compress[v], -1)
            size[0] -= 1
        else:
            k = q[1]
            out.append(find_kth(k))

    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: なぜ通常のヒープでは不足か

heapq（min-heap）は最小値を $O(\log N)$ で取れるが、最大値取得は $O(N)$。両方同時 + $k$ 番目は実現不可。

Step 2: 座標圧縮で値域を圧縮

値が $10^9$ まであるため、実際の出現値を昇順ソートして 1〜M にマッピング。同じ値が複数ある場合も BIT の各インデックスが その値の個数 を管理する。

Step 3: BIT で順序統計木を実現

クエリ	操作	計算量
追加	`bit_update(compress[x], 1)`	$O(\log M)$
最小削除	`find_kth(1)` + update	$O(\log M)$
最大削除	`find_kth(size)` + update	$O(\log M)$
k番目	`find_kth(k)`	$O(\log M)$

Step 4: find_kth の二分探索原理

BIT の木構造を利用して $O(\log M)$ で $k$ 番目を求める。bit[nxt] は区間 (pos, pos+(1<<i)] の合計。累積和が $k$ 未満の間は右へ進む。

よくあるミス

ミス	原因	正しい書き方
`sorted_vals[pos]` で IndexError	BIT 二分探索の終端条件ミス	`pos` は 0-indexed に注意
find_kth でループ範囲ミス	`log = M.bit_length()` の計算	`range(log, -1, -1)`
重複値を座標圧縮で削除しない	BIT で同値を区別	`sorted(set(vals))` で重複除去
size の更新忘れ	クエリ 2, 3 後に size を減らさない	`size[0] -= 1` を忘れない

次のステップ

発展問題: 「区間 $[l, r]$ の中央値をリアルタイムで求める」（二本のヒープを使う中央値維持アルゴリズム）
応用: Merge Sort Tree を用いた複数列の統合 $k$ 番目クエリ

Day 077-Q1 — Double-Ended Priority Queue（MinMaxHeap + BIT 順序統計木）

問題

制約