2232. The Floor Key and How Many Copies

A multiset of integers starts empty. Then q operations arrive, one per line:

add v put another copy of v in del v take ONE copy of v out; it is guaranteed to be there fm v print the floor of v and how many copies of it are stored

The floor of v is the largest stored key at most v. Print none alone when there is none, so an fm line holds either two numbers or one word.

add 10 add 10 fm 20 -> 10 2 fm 10 -> 10 2 del 10 fm 20 -> 10 1

## The complexity contract

add O(log q) del O(log q) fm O(log q)

## Why the two halves of the answer need different queries

The floor is about ORDER and the count is about MEMBERSHIP, and an ordered structure has to answer both.

floor(v) = c = atMost(v); none if c == 0, else the c-th smallest key copies(x) = atMost(x) - less(x)

So the second half is the DIFFERENCE of two prefix sums at the same key, which is what a Fenwick tree of counts gives naturally: the count stored at one compressed index. A set of distinct keys could not answer it at all, which is the difference between a set and a multiset.

Note that the count must be taken at the FLOOR, not at v. On add 1, add 2, add 2, fm 1 the floor of 1 is 1 with one copy, and asking at v would be right only because v happens to be stored. The declared test add 1, add 2, add 2, fm 2, fm 1, fm 3 separates the two readings.

## What most people try first

A hash map from value to count, which answers the COUNT in constant time and cannot answer the floor at all, because a hash map knows nothing about order. The usual repair, keeping a sorted array of the distinct keys beside the map, makes the floor O(log q) and every insertion of a NEW key O(q).

That is the general shape of this topic: the count wants a hash and the floor wants an order, and a Fenwick tree of counts over compressed values gives both at once.

## The method

``` compress the values, which the problem allows because every operation is read before the first one runs cnt is a Fenwick tree indexed by compressed value, holding the number of copies

add v: +1 at the index of v del v: -1 at the index of v fm v: c = atMost(v) if c == 0: none else: f = the c-th smallest key, by one binary descent print f and ( atMost(f) - less(f) ) ```

## Why deleting one copy and deleting all copies are different operations

del here removes ONE copy, so the floor is unchanged while any copy remains and only moves when the last one goes. That is the behaviour the declared test add 2, add 2, fm 2, del 2, fm 2, del 2, fm 2, fm 3 traces: 2 2, then 2 1, then none, then none.

A version where a deletion removes every copy at once gives a different answer on that very stream, which is what problem 2250 is built on.

## Cost

O(q log q) time and O(q) memory. A value of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and a count is at most q = 200000, so neither quantity needs 64 bits.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - Every operation is `add v`, `del v` or `fm v`. - A `del v` is only given when at least one copy of `v` is stored. - Every value that can ever be stored appears in the input, so the values are known in advance.