Overview

This problem requires performing insertions and deletions on a dynamically changing multiset, and counting the number of times a deleted element matches the “median” at that point. When the number of elements is \(n\), the median is defined as the \(\lceil n/2 \rceil\)-th value in ascending order.

Analysis

1. Naive Approach and Its Limitations

If we sort the multiset for each query to find the median, it costs \(O(Q \log Q)\) per query, resulting in \(O(Q^2 \log Q)\) overall, which is too slow for the constraint \(Q = 2 \times 10^5\). Additionally, if we maintain order using Python’s list insert and pop, each operation costs \(O(Q)\), leading to \(O(Q^2)\) overall, which results in TLE (Time Limit Exceeded).

2. Identifying Required Operations

To solve this problem efficiently, we need a data structure that can perform the following operations quickly: 1. Insert a value \(X\) 2. Delete a value \(X\) 3. Retrieve the \(k\)-th smallest value (to identify the median)

3. Using Coordinate Compression

Since values \(X_i\) can be as large as \(10^9\), we cannot directly use them as array indices. However, the number of distinct values appearing in queries is at most \(Q\) types (\(2 \times 10^5\)). By sorting all values that appear in advance and assigning numbers \(1, 2, 3, \dots\) in ascending order — a technique called coordinate compression — we can convert values into integers in a manageable range.

4. Management with a Fenwick Tree (BIT)

For the indices after coordinate compression, we manage how many of each value exist in the multiset using a Fenwick Tree (Binary Indexed Tree; BIT). - Insertion/Deletion: Simply add \(+1\) or \(-1\) to the corresponding index in the BIT, costing \(O(\log Q)\). - Retrieving the \(k\)-th value: The prefix sum on the BIT represents “how many elements are less than or equal to that value.” By finding the smallest index where the prefix sum is at least \(k\) using binary search (or binary search on the BIT / doubling method), we can identify the median in \(O(\log Q)\).

Algorithm

1. Preparation: Read all queries in advance, apply coordinate compression to the appearing \(X_i\) values, and map original values to indices \(1 \dots M\).
2. Query Processing:
   • + X:
     • Increment the count at the index corresponding to \(X\) in the BIT by \(+1\).
     • Increment the current number of elements current_n by \(+1\).
   • - X:
     • Compute the rank of the median \(k = \lceil current\_n / 2 \rceil\) from the current number of elements.
     • Use binary search on the BIT (doubling method) to find the index of the current \(k\)-th smallest value.
     • If that index matches the index of \(X\), count it as a median hit.
     • Decrement the count at the index corresponding to \(X\) in the BIT by \(-1\).
     • Decrement current_n by \(-1\).
3. Output: Print the final count.

Complexity

• Time Complexity: \(O(Q \log Q)\)
  • Sorting for coordinate compression takes \(O(Q \log Q)\).
  • For each query, BIT update and \(k\)-th value search take \(O(\log Q)\).
  • The overall complexity is \(O(Q \log Q)\), which is sufficiently fast.
• Space Complexity: \(O(Q)\)
  • The dictionary for coordinate compression, the BIT array, and storing queries use \(O(Q)\) memory.

Implementation Notes

• Binary search on the BIT (doubling method): By leveraging the structure of the BIT and checking prefix sums from the highest bit downward, we can find the \(k\)-th element in \(O(\log Q)\), which is faster than a standard binary search (\(O(\log^2 Q)\)).

• Fast I/O: In Python, reading all input at once using sys.stdin.read().split() can reduce execution time.

  Source Code

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()

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