概要

動的に変化する多重集合に対して要素の追加と削除を行い、削除される要素がその時点での「中央値」と一致する回数を求める問題です。要素数が \(n\) のとき、中央値は昇順で \(\lceil n/2 \rceil\) 番目の値と定義されます。

考察

1. 素直なアプローチとその限界

クエリごとに多重集合をソートして中央値を求めると、1回あたり \(O(Q \log Q)\)、全体で \(O(Q^2 \log Q)\) かかり、制約の \(Q = 2 \times 10^5\) では間に合いません。 また、Pythonのリストの insert や pop を使って順序を維持する場合も、1回あたり \(O(Q)\) かかるため、全体で \(O(Q^2)\) となり TLE（実行時間制限超過）となります。

2. 必要な操作の整理

この問題を効率的に解くためには、以下の操作を高速に行えるデータ構造が必要です。 1. 値 \(X\) の追加 2. 値 \(X\) の削除 3. \(k\) 番目に小さい値の取得（中央値を特定するため）

3. 座標圧縮の利用

値 \(X_i\) は最大 \(10^9\) と非常に大きいため、値をそのまま配列のインデックスとして使うことはできません。しかし、クエリに登場する値の種類は最大でも \(Q\) 種類（\(2 \times 10^5\) 個）です。 あらかじめ出現するすべての値をソートし、小さい順に \(1, 2, 3, \dots\) と番号を割り当てる座標圧縮を行うことで、値を扱いやすい範囲の整数に変換できます。

4. フェニック木（BIT）による管理

座標圧縮した後のインデックスに対して、各値が多重集合の中にいくつ存在するかをフェニック木（Binary Indexed Tree; BIT）で管理します。 - 追加・削除: BITの該当インデックスの値を \(+1\) または \(-1\) するだけなので \(O(\log Q)\) です。 - \(k\) 番目の値の取得: BIT上の累積和は「その値以下の要素が何個あるか」を表します。累積和が \(k\) 以上になる最小のインデックスを二分探索（またはBIT上の二分探索/倍増法）で探すことで、中央値を \(O(\log Q)\) で特定できます。

アルゴリズム

1. 準備: すべてのクエリを先読みし、登場する \(X_i\) を座標圧縮して、元の値と \(1 \dots M\) のインデックスを対応させます。
2. クエリ処理:
   • + X:
     • \(X\) に対応するインデックスのカウントを BIT で \(+1\) する。
     • 現在の要素数 current_n を \(+1\) する。
   • - X:
     • 現在の要素数から中央値の順位 \(k = \lceil current\_n / 2 \rceil\) を計算する。
     • BIT上の二分探索（倍増法）を用いて、現在の \(k\) 番目に小さい値のインデックスを求める。
     • そのインデックスが \(X\) のインデックスと一致すれば、中央値ヒットとしてカウントする。
     • \(X\) に対応するインデックスのカウントを BIT で \(-1\) する。
     • current_n を \(-1\) する。
3. 出力: 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(Q \log Q)\)
  • 座標圧縮のためのソートに \(O(Q \log Q)\)。
  • 各クエリに対して、BITの更新と \(k\) 番目の値の探索が \(O(\log Q)\)。
  • 全体で \(O(Q \log Q)\) となり、十分に高速です。
• 空間計算量: \(O(Q)\)
  • 座標圧縮用の辞書やBITの配列、クエリの保存に \(O(Q)\) のメモリを使用します。

実装のポイント

• BIT上の二分探索（倍増法）: BITの構造を利用して、上位ビットから順に累積和を確認していくことで、通常の二分探索（\(O(\log^2 Q)\)）よりも高速な \(O(\log Q)\) で \(k\) 番目の要素を見つけることができます。

• 高速な入出力: Pythonの場合、sys.stdin.read().split() を使って一括で入力を読み込むことで、実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # Read all input at once and split into tokens for fast processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    Q = int(input_data[0])
    if Q == 0:
        sys.stdout.write('0\n')
        return
    
    # Extract query types and values using slicing
    # types: ['+', '+', '-', ...]
    # raw_x: [10, 20, 10, ...]
    types = input_data[1::2]
    raw_x = [int(x) for x in input_data[2::2]]
    
    # Coordinate compression: map each unique value to a 1-based index
    # This is necessary because values X_i can be as large as 10^9
    unique_x = sorted(set(raw_x))
    val_to_idx = {x: i + 1 for i, x in enumerate(unique_x)}
    
    # Pre-map all query values to their compressed indices for efficiency
    x_indices = [val_to_idx[x] for x in raw_x]
    
    # Fenwick tree (Binary Indexed Tree) to maintain counts of elements in the multiset
    n_bit = len(unique_x)
    bit = [0] * (n_bit + 1)
    
    # Precompute the largest power of 2 for binary lifting on the BIT
    max_pow2 = n_bit.bit_length() - 1
    
    hit_count = 0
    current_n = 0
    
    # Process queries sequentially
    for i in range(Q):
        t = types[i]
        x_idx = x_indices[i]
        
        if t == '+':
            # Addition query: increment count in BIT and update total size
            idx = x_idx
            while idx <= n_bit:
                bit[idx] += 1
                idx += idx & (-idx)
            current_n += 1
        else:
            # Deletion query:
            # 1. Check if the value being deleted is the median of the current multiset
            # Median position is defined as ceil(n / 2)
            k = (current_n + 1) // 2
            
            # Use binary lifting on the BIT to find the compressed index of the k-th smallest element
            # This is an O(log N) operation
            idx = 0
            temp_k = k
            for j in range(max_pow2, -1, -1):
                next_idx = idx + (1 << j)
                if next_idx <= n_bit:
                    val = bit[next_idx]
                    if val < temp_k:
                        idx = next_idx
                        temp_k -= val
            
            # The k-th smallest element's compressed index is idx + 1
            if idx + 1 == x_idx:
                hit_count += 1
            
            # 2. Perform the deletion: decrement count in BIT and update total size
            idx = x_idx
            while idx <= n_bit:
                bit[idx] -= 1
                idx += idx & (-idx)
            current_n -= 1
            
    # Output the total number of "median hits"
    sys.stdout.write(str(hit_count) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。