2250. Remove Every Copy at Once

A collection of integers starts empty and may hold several copies of the same value. 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 wipe v take EVERY copy of v out, and print how many were removed size print how many copies are stored in total

A wipe of a value with no copies removes nothing and prints 0.

add 10 add 10 add 3 wipe 10 -> 2 size -> 1 wipe 10 -> 0 size -> 1

## Why del and wipe are genuinely different operations

Problem 2232 ends by noting that removing one copy and removing all of them give different answers on the same stream, and could not show it, because a floor query returns a value and a value is unaffected by how many copies back it. This problem is that distinction made observable: on the stream above, four del 10 operations would be needed to achieve what one wipe 10 does, and size reads the difference straight out.

## What most people try first

A loop: while the collection contains v, remove one copy. It is correct, and its cost is O(count * log q) for one operation, which looks acceptable until you count the whole run. It is in fact fine OVERALL, by an amortised argument given below, and it is still the wrong thing to write, because the count is available in one step and the loop makes a wipe of 200000 copies take 200000 tree updates instead of one.

The other instinct, scanning a sorted array and shifting the tail down, is O(q) per operation and up to 2 * 10^10 element moves across the run.

## The method

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 a Fenwick tree of how many copies of each compressed value are stored, plus a running total m:

i = the position of v n = prefixSum(i) - prefixSum(i - 1) the count at that one position wipe: add -n at position i, m -= n, print n del: add -1 at position i, m -= 1 size: print m

So a wipe is a SINGLE Fenwick update whatever the count, which is the point.

## Why one update is enough, and what the loop really costs

A Fenwick tree update adds a delta to one position and repairs log q nodes above it. Nothing about it cares whether the delta is -1 or -200000, so removing every copy costs exactly what removing one costs. The loop version is not actually slow across a whole run, because every copy it removes was inserted by some earlier add and there are at most q of those, so the total extra work is O(q log q) amortised. It is worth being able to make that argument and still preferring the one-update version, since the amortised bound says nothing about a single operation finishing promptly.

## The boundary that breaks a careless implementation

Wiping a value that is absent, and wiping the same value twice. Both must print 0 and change nothing, and a size that is decremented by the count BEFORE the count is checked goes negative and stays wrong for the rest of the run.

## 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. - A `wipe v` may name a value with no copies stored. - Every operation is `add v`, `del v`, `wipe v` or `size`. - Every value that can ever be stored appears in the input, so the values are known in advance.