Overview

This problem requires counting the number of times the median matches the deleted value at the moment just before deletion, while adding and removing values from a multiset through queries.
To efficiently compute the median at each point in time, we use coordinate compression + Fenwick Tree (BIT).

Analysis

First, for each deletion query - x, we need to determine the “current median.”
The median is the \(\lceil n/2 \rceil\)-th element in ascending order, where \(n\) is the number of elements. In code, this is the \(k = (n+1)//2\)-th value.

Why a Naive Solution Is Too Slow

For example, if we were to: - Re-sort the multiset each time, or - Insert/delete from a list and look up the median position,

each query would take \(O(n)\) or more, which is too slow for \(Q \le 2\times10^5\) (TLE).

Key Insight

What we need is “the relative ordering of values” and “how many of each value exist.”
Therefore:

1. Collect all \(X_i\) in advance, sort and deduplicate them (coordinate compression).
2. Use a Fenwick Tree to manage counts indexed by compressed coordinates.
3. Use prefix sums on the Fenwick Tree to find the “\(k\)-th element” via a binary-search-like method.

This allows additions, deletions, and median queries all in \(O(\log Q)\).

Algorithm

1. Read all queries in advance and collect the appearing values into vals.
2. Sort vals and remove duplicates to create vals_sorted (coordinate compression).
   • comp[x] = compressed index (1-indexed)
3. Prepare a Fenwick Tree fw, where fw[i] represents “the count of compressed value i.”
4. Maintain size as the current number of elements.
5. Process each query in order:
   • + x: fw.add(comp[x], 1), size += 1
   • - x:
     1. Compute \(k = (size+1)//2\) (the rank of the current median).
     2. Obtain the compressed position of the \(k\)-th element with mid_idx = fw.kth(k).
     3. If the actual value vals_sorted[mid_idx-1] equals x, increment the answer by 1.
     4. Then perform fw.add(comp[x], -1), size -= 1.

fw.kth(k) is a function that returns “the smallest index where the prefix sum first reaches \(k\) or more,” which directly corresponds to the \(k\)-th element.

Complexity

• Time complexity: \(O(Q \log Q)\)
  (Sorting for coordinate compression \(O(Q\log Q)\) + Fenwick Tree operations per query \(O(\log Q)\))
• Space complexity: \(O(Q)\)
  (Query storage, compression array, BIT)

Implementation Notes

• The median must be determined on the set before deletion (check first, then delete).

• The problem’s median definition is “for an even number of elements, the smaller of the two middle values,” so the rank is always \(k=(size+1)//2\).

• Implementing the Fenwick Tree as 1-indexed makes it easier to handle.

• The kth implementation uses the internal array of the BIT to locate the position in a binary-search-like manner. This enables rank queries in \(O(\log N)\).

  Source Code

import sys


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def kth(self, k):
        idx = 0
        bit_mask = 1 << (self.n.bit_length() - 1)
        while bit_mask:
            nxt = idx + bit_mask
            if nxt <= self.n and self.bit[nxt] < k:
                k -= self.bit[nxt]
                idx = nxt
            bit_mask >>= 1
        return idx + 1


def main():
    input = sys.stdin.readline
    Q = int(input())
    queries = []
    vals = []
    for _ in range(Q):
        op, x = input().split()
        x = int(x)
        queries.append((op, x))
        vals.append(x)

    vals_sorted = sorted(set(vals))
    comp = {v: i + 1 for i, v in enumerate(vals_sorted)}

    fw = Fenwick(len(vals_sorted))
    size = 0
    ans = 0

    for op, x in queries:
        idx = comp[x]
        if op == '+':
            fw.add(idx, 1)
            size += 1
        else:
            k = (size + 1) // 2
            mid_idx = fw.kth(k)
            if vals_sorted[mid_idx - 1] == x:
                ans += 1
            fw.add(idx, -1)
            size -= 1

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.