2251. Copies and Different Keys

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 both print two numbers: how many copies are stored, and how many DIFFERENT values are stored

add 10 both -> 1 1 add 10 both -> 2 1 two copies, one different value add 3 both -> 3 2

## What most people try first

One counter. It is tempting because the two numbers agree on every stream with no repeats, which is most streams a person writes by hand, and they come apart the first time a value arrives twice.

The next instinct is a hash map from value to count, incrementing a distinct counter when an entry is created and decrementing it when one is deleted. That is in fact a correct and fast answer to this exact problem. It is worth seeing why it is a dead end: change both to "how many different values lie in [a, b]", which is problem 2244, and the hash map has nothing to offer, because it has no order. The structure below answers both questions with no change at all.

## The method: two trees, one update

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. A count tree holds MULTIPLICITIES, and no arithmetic on a prefix of multiplicities recovers how many different keys are below a point: a prefix sum of 2 could be one value twice or two values once each, and the tree has thrown away which. So keep a SECOND Fenwick tree over the same compressed positions holding 1 wherever a value has at least one copy stored:

add v -> if the count at v was 0 before this copy arrived, add 1 del v -> if the count at v reaches 0 as this copy leaves, subtract 1

Those two crossings are the only moments it can change, because a multiplicity moves one copy at a time and so crosses zero only on the first copy in and the last copy out. Updating there preserves the invariant with no rescanning.

Then both prints

copies = the full prefix sum of the count tree, or a running total different = the full prefix sum of the presence tree

## Why the crossings are the whole argument

The invariant is "the presence tree holds 1 exactly where the multiplicity is positive". If it holds before an operation, then an add that takes a count from 0 to 1 is the only add that can break it and it is exactly the one that updates, and a del that takes a count to 0 is the only del that can break it and it is exactly the one that updates. So the invariant holds after every operation, by induction over the stream, and a prefix sum of the presence tree counts different values by definition.

## The boundary that breaks a careless implementation

Reading the count AFTER the update rather than before. An add must ask "was it zero before this copy", and an implementation that inserts first and then checks for 1 happens to work, while an implementation that inserts first and checks for 0 never fires at all. For del the test runs the other way: it must ask whether the count reaches zero AFTER the copy leaves. The declared tests remove two copies of one value one at a time so the two cases are separated.

## Cost

O(q log q) time and O(q) memory, or O(1) per query if both totals are kept as running counters. A key of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and both answers are 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 `both`. - Every value that can ever be stored appears in the input, so the values are known in advance.