2241. The kth Smallest Distinct Key

A collection of integers starts empty. 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 kd k print the kth smallest DISTINCT stored key, or none

Distinct means copies do not count. With 10, 3 and another 10 stored there are two distinct keys, so kd 1 is 3, kd 2 is 10, and kd 3 is none.

add 10 add 3 add 10 kd 1 -> 3 kd 2 -> 10 kd 3 -> none

## What most people try first

The ordinary count tree, with a binary descent for rank k. It gives the kth smallest COUNTING copies, which is a different question: on the example above that descent answers kd 2 with 10 by coincidence and answers kd 3 with 10 as well, because the third stored copy is a second 10. Problem 2234 is exactly that query, and the difference between the two is the whole content here.

The second instinct is to keep a separate sorted list of the distinct keys. It answers the query instantly and pays O(q) per update to insert into or remove from the middle, so 200000 operations is up to 2 * 10^10 element moves.

## The method: a tree of presence, not of counts

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 TWO Fenwick trees over the same compressed positions:

TREE[i] how many copies of value i are stored (a multiplicity) PTREE[i] 1 if value i has at least one copy stored, else 0

PTREE is NOT TREE with the numbers squashed, and it cannot be derived from a prefix sum of TREE. It has to be maintained, and the only moments it changes are the two transitions:

add v -> if the count at v was 0 before this copy, add 1 to PTREE at v del v -> if the count at v reaches 0 after this copy goes, subtract 1

Then the kth smallest distinct key is the ordinary binary descent run on PTREE instead of TREE.

## Why the transitions are the whole correctness argument

PTREE must hold a 1 exactly when the multiplicity is positive. Multiplicity only ever changes by one copy at a time, so it crosses zero only on the first insert and on the last delete, and updating PTREE at those two moments keeps the invariant with no rescanning. Given the invariant, a prefix sum of PTREE counts distinct keys rather than copies, so the same descent that finds the kth copy now finds the kth distinct key.

## The boundary that breaks a careless implementation

Deleting one copy of a value that has several. The distinct ranking must not move: with 4, 4, 8 stored, deleting one 4 leaves kd 1 as 4, and only deleting the second one makes it 8. An implementation that subtracts from PTREE on every del reports 8 one delete early, and an implementation that adds to PTREE on every add double-counts a repeated value and pushes every later rank one place along.

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