2239. The Total of Every Key At Most x

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 sle x print the total of every stored key that is at most x

Copies count, so two copies of 3 contribute 6. Note that x need not be stored: the question is about order, not membership.

add 10 add 3 sle 10 -> 13 sle 9 -> 3 sle 2 -> 0 del 3

## Why this is not problem 2001 again

Problem 2001 keeps running totals over POSITIONS in an array: cell 7 holds a number and sum 3 7 adds up cells 3 to 7. The index is given. Here the cut is by VALUE, and the same value can arrive several times and leave again, so there is no fixed cell to update. Turning one into the other is exactly what coordinate compression does, and that step is the content of this problem.

## What most people try first

Scanning the whole collection on every query, which is O(m) per query and O(q^2) overall: 200000 operations is up to 4 * 10^10 comparisons. Keeping a sorted array with a prefix-sum array beside it is the next instinct, and the prefix sums have to be rebuilt after every single update, which is O(q) each time and no better.

## The method

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Sort the distinct values, give each one a position in that sorted list, and keep a Fenwick tree STREE over those positions in which position i carries

STREE contribution of i = value(i) * (number of copies of value(i) stored)

An add v adds v at position of v, a del v subtracts v there, and

sle x = prefix sum of STREE up to the last position whose value is <= x

The "last position whose value is at most x" is one binary search over the sorted distinct values, and the prefix sum is one Fenwick walk, so the whole query is O(log q).

## Why it is correct

The compressed positions are in increasing value order, so the stored keys at most x are exactly those at positions up to that boundary, with no gaps and nothing in between. That is why a prefix is the right shape of answer at all: the set of keys the query asks about is always an initial run of the order, and never a scattered selection. Summing a prefix of STREE therefore adds up value * count over precisely those keys, which is their total with duplicates counted once per copy. The binary search uses <= rather than < so that a stored x is included, which is what makes sle 10 answer 13 rather than 3 above.

## Overflow

200000 keys of 10^9 total 2 * 10^14, far past the signed 32 bit limit of 2147483647, so the tree nodes and the answer have to be 64 bit. Note that the VALUES themselves are fine in 32 bits; it is only their total that is not, which is why this is easy to miss.

## Cost

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

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