2240. How Far Apart the Two Halves Are

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 bal print the spread between the collection's two halves

With m keys stored in sorted order, the LOWER half is the first m / 2 of them with integer division and the UPPER half is everything else, so for odd m the middle key belongs to the upper half. The spread is the total of the upper half minus the total of the lower half. An empty collection has a spread of 0.

add 10 keys 10 lower (none) upper 10 bal -> 10 add 2 keys 2 10 lower 2 upper 10 bal -> 8 add 6 keys 2 6 10 lower 2 upper 6 10 bal -> 14

## What most people try first

Sorting the stored keys on every bal and adding up the two halves. That is O(m log m) per query and O(q^2 log q) overall, which 200000 operations does not survive. Keeping two heaps, one per half, is the next instinct and it falls over on del: the key being deleted can be buried anywhere inside either heap, and a binary heap cannot remove an element it is not looking at.

## The method: one subtraction, one descent

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Compress them and keep two Fenwick trees over the same compressed positions, TREE holding multiplicities and STREE holding value * multiplicity. Write S for the total of everything and L for the total of the lower half. Then

m = the number of stored copies h = m / 2 integer division L = the total of the h smallest keys upper = S - L bal = upper - L = S - 2 * L

S is the whole of STREE, one prefix sum. L is the accumulating descent: run the ordinary binary search for the hth smallest on TREE, adding up STREE over exactly the subtrees stepped into, and finish with rem * value(stopping position).

## Why S - 2 * L is right, and why the halves must be cut by rank

The two halves partition the collection, so upper = S - L with no overlap and nothing left out, and upper - L = S - 2L. One descent and one prefix sum therefore answer a question that names both halves.

Cutting by VALUE instead of by rank is the trap. With 5, 5, 5 stored, h = 1, so the lower half is one copy of 5 and the spread is 10 - 5 = 5. Anyone who takes "everything at most the median" as the lower half gets all three copies and answers -15. The duplicated value straddles the boundary, and only a rank-based cut can split it.

## Overflow

200000 keys of 10^9 total 2 * 10^14, which is far past the signed 32 bit limit of 2147483647. The doubling makes it worse: 2 * L alone reaches 4 * 10^14. Every tree node, the accumulator in the descent and the printed answer are 64 bit.

## The boundary that breaks a careless implementation

m = 0 and m = 1. With m = 0, h = 0, so the descent must not run at all and the answer is 0. With m = 1, h = 0, so the single key is in the UPPER half and the answer is that key itself, which is what makes the integer division m / 2 rather than (m + 1) / 2 the right choice here.

## Cost

O(q log q) time and O(q) memory.

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 `bal`. - Every value that can ever be stored appears in the input, so the values are known in advance.