2234. The kth Smallest While the Set Changes

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 kth k print the kth smallest stored key, or none

Copies count. With 2, 2 and 5 stored, the 1st smallest is 2, the 2nd smallest is also 2, and the 3rd is 5.

add 10 add 3 kth 1 -> 3 kth 2 -> 10 kth 3 -> none del 3

## What most people try first

A sorted array and an index. The lookup a[k - 1] is as fast as anything can be, and it is the UPDATES that sink it: putting a value into the middle of a sorted array shifts every element after it, and taking one out shifts them back. That is O(q) work per update, so 200000 operations is up to 2 * 10^10 element moves.

A heap does not help either. It knows its own extreme and nothing about the element two places in, so a heap can answer kth 1 and no other k. That is the gap between the heaps block and this one.

## The reduction, and why the values may be compressed

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. So sort the distinct values once, call each value by its position in that sorted list, and keep an array cnt indexed by that position holding how many copies of the value are stored. Put cnt inside a Fenwick tree, and

kth(k) = the smallest position whose prefix sum of counts is at least k

which is one BINARY DESCENT of the tree: start at the highest power of two, and take a step down whenever the count in that subtree is still smaller than what remains of k.

## Why the descent is correct

The prefix sum up to position i is exactly how many stored keys are at most the value at i, and it only grows as i grows. So the positions whose prefix sum reaches k form a suffix, and the first of them is the answer. The descent maintains "rem copies still to be passed" and only steps into a subtree when that whole subtree can be passed, which is the same monotone search a binary search over prefix sums would do, done in one walk instead of log walks each costing log.

## The boundary that breaks a careless implementation

k larger than the number of stored keys, and k = 0. Both must print none, and a descent that is not guarded walks off the end of the tree and returns the largest key instead, which looks right on every other test.

## 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 the counts in the tree are at most q = 200000, so nothing here needs 64 bits.

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