2236. The Middle Key of a Changing Collection

A collection of integers starts empty. Then q operations arrive, one per line:

add v put another copy of v into the collection del v take one copy of v out of the collection med print the LOWER MEDIAN of the stored keys, or none

With m keys stored, the lower median is the key at rank (m + 1) / 2 counting from the smallest, rounding down. For an odd m that is the middle key; for an even m it is the lower of the two middle keys, so there is never a tie to break and never an average to round.

add 10 keys 10 -> med -> 10 add 3 keys 3 10 -> med -> 3 add 7 keys 3 7 10 -> med -> 7

## Why this is not problem 719 again

Problem 719 takes the median of every window of a FIXED width over an array that never changes. The width being fixed is what makes two heaps work there: each slide pushes one key and pops one, and the two halves stay the same size. Here add and del arrive in any order and the collection grows and shrinks, so there is no fixed split to maintain.

## What most people try first

Sorting the collection on every med. That is O(m log m) per query and O(q^2 log q) overall, which 200000 operations does not survive. The two-heaps idea is the next instinct and it needs a rebalance after every single update, plus a way to delete a key that is buried in the middle of one of the heaps, which a binary heap cannot do.

## The method: the median is just a rank

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Compress them, keep a Fenwick tree of how many copies of each compressed value are stored, and maintain m. Then

med = the ((m + 1) / 2)th smallest key, integer division

and that comes out of one binary descent of the tree. The structure never needs to know that the rank it is being asked for is the middle one.

## Why that rank is the lower median

For odd m = 2t + 1 the formula gives t + 1, which has t keys below it and t above, so it is the middle one. For even m = 2t it gives t, the lower of the two middle keys, exactly as the statement asks. Writing m / 2 instead gives t for odd m, which is one below the middle, and a collection of one key would then report rank 0 and print nothing at all.

## The boundary that breaks a careless implementation

An empty collection. (0 + 1) / 2 is 0, and rank 0 does not exist, so med must print none rather than descend. The declared tests include a collection that is emptied by deletions and then queried again.

## Cost

O(q log q) time and O(q) memory. A key of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and m is at most q = 200000.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - A `del v` always names a value with at least one copy currently stored. - Every operation is `add v`, `del v` or `med`. - Every value that can ever be stored appears in the input, so the values are known in advance.