2259. The Next k Keys in Order

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 of the collection walk x k print the k smallest stored keys that are at least x, in increasing order, on one line separated by single spaces

Copies count, so three copies of 2 print as 2 2 2. If fewer than k stored keys are at least x, print all of them. If there are none, or if k is 0, print the word none.

add 10 add 3 add 7 copies 3 7 10 walk 3 2 -> 3 7 walk 4 2 -> 7 10 walk 11 1 -> none

## What most people try first

Keeping the collection in a sorted array, finding x by binary search and copying k entries from there. The reading is exactly right; the array is the problem, because every add and every del shifts its tail, which is O(q) per update and up to 2 * 10^10 element moves across 200000 operations.

The second instinct is to call the successor query k times, feeding each answer back in. That is correct and it is subtly wrong with duplicates: a strict successor SKIPS the other copies of the key it just returned, so three copies of 2 would print 2 and then whatever comes after all of them, which is not what the statement asks for.

## The method: one prefix count, then k descents

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 turn the start of the walk into a RANK:

start = the number of stored copies strictly less than x then for t = 1, 2, ... up to k: the copy at rank start + t, if that rank exists

So the walk is a prefix count and then k independent binary descents, each O(log q), and because each one asks for a rank rather than for "the next key after this value", duplicates come out one at a time exactly as required.

## Why a loop over k is acceptable here and was not in problem 2246

The constraint is k <= 10. That is the whole argument, and it is the reason the constraint is stated so tightly: 10 log q per query is about 180 tree steps, while problem 2246 allows k up to 200000 and so has to collapse the loop into a single descent. A loop whose bound is a small constant is not a complexity problem; a loop whose bound is the input size is. Being able to tell those apart is the point of the two problems sitting near each other.

## The boundary that breaks a careless implementation

Running out of keys partway through. The walk must stop as soon as a rank does not exist and print what it has, rather than printing none for the missing ones or repeating the largest key. And k = 0 prints none, not an empty line, which is a real difference to a judge comparing bytes.

## Cost

O(q log q) time and O(q) memory, with at most 10 descents per query. 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` - `-1000000000 ≤ x ≤ 1000000000` - `0 ≤ k ≤ 10` - A `del v` always names a value with at least one copy currently stored. - Every operation is `add v`, `del v` or `walk x k`. - Every value that can ever be stored appears in the input, so the values are known in advance.