Day 052-Q5 — 順序統計木（BIT + 座標圧縮・insert/delete/kth/count クエリ）

2026-06-05 赤色 Master / Phase 8+ ★★★★★★★★★ 順序統計木 / BIT / 座標圧縮 / Skip List

問題

空の多重集合 $S$ に対して $Q$ 個のクエリを処理せよ：

  • insert x: 値 $x$ を $S$ に挿入する
  • delete x: 値 $x$ を $S$ から1つ削除する（必ず存在する）
  • kth x: $S$ の昇順 $x$ 番目（1-indexed）の値を出力せよ
  • count x: $S$ 中の $x$ 以下の要素数を出力せよ

制約

パラメータ範囲
$Q$$1 \le Q \le 2 \times 10^5$
insert/delete/count の値 $x$$-10^9 \le x \le 10^9$
kth の $x$$1 \le x \le |S|$
時間制限2秒

入出力例

入力例 1

8
insert 3
insert 1
insert 4
insert 1
kth 2
count 3
delete 1
kth 2

出力例 1

3
3
3

$S = \{1,1,3,4\}$ → 昇順2番目 = 3。3以下 = \{1,1,3\} → 3個。delete 1 → $S=\{1,3,4\}$ → 昇順2番目 = 3。

概念図: BIT による順序統計木（座標圧縮）

座標圧縮 + BIT による順序統計: S = {1, 1, 3, 4} 座標圧縮 元の値: {1, 3, 4} → sorted_vals = [1, 3, 4] 圧縮後: 1→1, 3→2, 4→3 (1-indexed) BIT（各圧縮値の個数） 圧縮位置: 1 2 3 BIT値（個数）: 2 1 1 ← {1,1,3,4} BIT 内部構造（tree[]） tree[1] = 2 tree[2] = 3 tree[3] = 1 tree[2]は[1..2]の和=3 kth(2) の計算（二分探索 on BIT） bit=1 (log₂3=1): nx=0+(1<<1)=2, tree[2]=3>=2 → 左 bit=0: nx=0+(1<<0)=1, tree[1]=2>=2 → 左 x+1 = 1 → sorted_vals[0] = 1 (圧縮位置1 → 元の値1) kth(2) = 1 ← 昇順2番目は1（{1,1,3,4}の2番目=1） count(3) の計算（3以下の個数） bisect_right([1,3,4], 3) = 2 bit_query(2) = tree[2] = 3 3以下の要素数 = 3 ← {1,1,3}の3個 O(log N) per query

ヒント（段階的開示）

ヒント1: 方向性
値の範囲 $[-10^9, 10^9]$ を直接 BIT に使うとメモリ爆発。 クエリ先読みで使われる値を収集し、座標圧縮（ソート + インデックス化）してから BIT で管理する。 kth クエリは BIT 上での二分探索 $O(\log N)$ で実現。
ヒント2: アプローチ
  • 全先読み: 全クエリを読み込み、insert/delete/count の値を収集
  • 座標圧縮: sorted_vals でソート、comp[v] = 1-indexed 位置
  • BIT: 位置 $i$ = 値 comp[v] の現在個数を管理
  • kth: BIT 上の二分探索（最上位ビットから貪欲に）
  • count: bisect_right(sorted_vals, x) で圧縮境界を求め bit_query()
ヒント3: BIT kth の実装 
def bit_kth(k):
    """BIT 上で k番目の位置（1-indexed）を返す"""
    x = 0
    log = M.bit_length()  # M = sorted_vals の長さ
    for i in range(log, -1, -1):
        nx = x + (1 << i)
        if nx <= M and tree[nx] < k:
            k -= tree[nx]
            x = nx
    return x + 1  # 1-indexed

# count x: x 以下の個数
from bisect import bisect_right
pos = bisect_right(sorted_vals, x)  # x 以下の圧縮インデックス数
result = bit_query(pos)

模範解答 (Python)

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    Q = int(input_data[idx]); idx += 1

    queries = []
    vals = []
    for _ in range(Q):
        op = input_data[idx]; idx += 1
        arg = int(input_data[idx]); idx += 1
        queries.append((op, arg))
        if op in ('insert', 'delete', 'count'):
            vals.append(arg)

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

    # BIT
    tree = [0] * (M + 2)

    def bit_add(i, v):
        while i <= M:
            tree[i] += v
            i += i & (-i)

    def bit_query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    def bit_kth(k):
        x = 0
        log = M.bit_length()
        for i in range(log, -1, -1):
            nx = x + (1 << i)
            if nx <= M and tree[nx] < k:
                k -= tree[nx]
                x = nx
        return x + 1  # 1-indexed

    out = []
    for op, arg in queries:
        if op == 'insert':
            bit_add(comp[arg], 1)
        elif op == 'delete':
            bit_add(comp[arg], -1)
        elif op == 'kth':
            ci = bit_kth(arg)
            out.append(str(sorted_vals[ci - 1]))
        else:  # count
            pos = bisect_right(sorted_vals, arg)
            out.append(str(bit_query(pos)))

    print('\n'.join(out))

main()

Step-by-Step 解説

1座標圧縮の前処理
全クエリを先読みして insert/delete/count で使う値を収集。ソート + 重複削除で sorted_vals を作成。 comp[v] = 1-indexed 位置 で元の値 → 圧縮インデックスに変換。
2BIT による個数管理
BIT の位置 $i$ = 圧縮インデックス $i$ の値の現在の個数。 insert: bit_add(comp[x], +1)、delete: bit_add(comp[x], -1)。
3kth の二分探索
最上位ビットから貪欲に探索。tree[nx] < k なら右へ（左側の和が k 未満）。 $O(\log M)$ で $k$ 番目の圧縮インデックスを特定 → sorted_vals[ci-1] で元の値を復元。
4count の境界処理
クエリ値 $x$ が sorted_vals に存在しなくても、bisect_right(sorted_vals, x) で 「$x$ 以下の圧縮インデックスの個数」を求め、bit_query(pos) に渡す。

計算量

前処理（座標圧縮）: $O(Q \log Q)$
insert/delete: $O(\log M)$ per query（$M \le Q$）
kth: $O(\log M)$ per query
count: $O(\log Q + \log M)$ per query
全体: $O(Q \log Q)$
空間: $O(Q)$

よくあるミス

ミス原因正しい書き方
kth の 0-indexed/1-indexed 混在BIT は 1-indexed, sorted_vals は 0-indexedsorted_vals[ci - 1]
count で bisect_left 使用$x$ と等しい値も含めるべきbisect_right(sorted_vals, x)
bit_kth のビット数M=0 のとき bit_length() = 0max(M.bit_length(), 1)
kth の引数を座標圧縮kth の引数は「順位」であって値でないkth は comp を使わない

次のステップ

  • 発展問題: 動的値追加（クエリ先読み不可）での順序統計 → Treap または Skip List の完全実装
  • 関連: 永続 BIT（Persistent BIT）による区間 $k$ 番目クエリ $O(\log^2 N)$
  • 応用: マージソート木（Merge Sort Tree）による区間 $k$ 番目 $O(\log^3 N)$

自己評価