2249. How Many Copies of a Key

A collection of integers starts empty, and it is a MULTISET: the same value may be stored several times over. 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 cnt v print how many copies of v are currently stored

A cnt of a value that was never stored is 0.

add 10 add 10 cnt 10 -> 2 del 10 cnt 10 -> 1 cnt 3 -> 0

## Why this is the problem the earlier ones were pointing at

Problems 2226 to 2233 all store duplicates and none of them can observe one. floor, ceiling and nearest all return a VALUE, and a value does not change when a second copy of it arrives, so the whole of pattern 1 behaves identically whether del removes one copy or all of them. Here the count IS the answer, so the distinction becomes visible for the first time.

Problem 242 asks the same question of a fixed array given once, which two binary searches answer. Here the copies arrive and leave between the queries.

## What most people try first

A hash map from value to count, which answers cnt in constant time and is the right answer to THIS problem alone. It is worth knowing why it stops working: the moment the question becomes "how many copies of the largest key below v", or "how many different keys are stored", a hash map has no order and cannot help. Problem 2232 is the first and problem 2251 is the second.

The second instinct, a sorted array scanned on every query, is O(m) per query and O(q^2) overall: 200000 operations is up to 4 * 10^10 comparisons.

## The method, in the structure the rest of the pattern needs

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 read one entry out of it:

i = the position of v among the sorted distinct values cnt(v) = prefixSum(i) - prefixSum(i - 1)

and 0 when v is not one of those distinct values at all.

## Why a difference of two prefix sums is a single entry

A Fenwick tree stores sums over blocks, not individual cells, so the count at one position is not stored anywhere directly. But the keys at positions 1 .. i minus the keys at positions 1 .. i - 1 leaves exactly position i, so the difference is that one count. Both walks are O(log q).

## The boundary that breaks a careless implementation

A value that is not in the compressed universe at all, and a value whose count has fallen back to 0. The binary search for i lands on the first position whose value is at least v, which may hold a DIFFERENT value, so the result has to be checked against v before it is used. Skipping that check reports the count of a neighbouring key, which on a dense collection looks almost right.

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