2252. The Two Ranks of One Key

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 two k print two answers for the same k: the kth smallest stored COPY the kth smallest DIFFERENT value using the word none for either one that does not exist

add 10 add 3 add 10 copies 3 10 10, different values 3 10 two 1 -> 3 3 two 2 -> 10 10 two 3 -> 10 none

Rank 3 is where they separate: there is a third copy and there is no third different value.

## What most people try first

One descent, used twice. The kth copy and the kth different value agree for every k on a collection with no repeats, and they agree for small k on many collections that do have repeats, so a solution that answers both from the count tree looks right until a rank reaches past the number of different values.

The second instinct is to keep a sorted list of the different values beside the multiset. That answers the second question instantly and costs O(q) on every update, since a value appearing for the first time has to be inserted into the middle of the list. Across 200000 operations that is up to 2 * 10^10 element moves.

## The method: the same descent on two different trees

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.

The kth smallest copy is the ordinary binary descent on the COUNT tree, and the kth smallest different value is the identical descent run on the PRESENCE tree. Nothing else changes: same walk, same guard, different array.

k = 3, copies 3 10 10 count tree positions carry 1 and 2 -> prefix reaches 3 at 10 -> 10 presence tree positions carry 1 and 1 -> prefix never reaches 3 -> none

## Why the same walk works on both

A Fenwick descent for rank k needs only that the array it walks is non-negative, so that prefix sums grow as the index grows. Both trees satisfy that, and the descent therefore returns the first position whose prefix reaches k in whichever quantity that tree is counting. Choosing the tree chooses the question, which is exactly the right separation of concerns.

## The boundary that breaks a careless implementation

The two ranges differ. The largest valid k for the first answer is the number of copies and for the second it is the number of different values, and the second is never larger. So a single guard, written once against the number of copies, lets the presence descent run past the end of its own data and return the largest value instead of none. k = 0 must be none for both.

## 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 nothing here adds two keys together.

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