882. The kth Smallest After Every Arrival
Values arrive one at a time. After each arrival, print the kth SMALLEST of
everything that has arrived so far, counting from 1 and counting duplicates
separately. Until k values have arrived there is no such value, so print
none for those lines.
n = 5, k = 2, arrivals 5 1 4 2 3 -> none, 5, 4, 2, 2
n = 4, k = 1, arrivals 7 2 9 1 -> 7, 2, 2, 1
n = 3, k = 2, arrivals -1000000000 1000000000 0 -> none, 1000000000, 0
Trace the first one. After 5 only one value exists, so none. After 1
the set is 1 5 and the 2nd smallest is 5. After 4 the set is 1 4 5 and
the 2nd smallest is 4. After 2 the set is 1 2 4 5, giving 2, and after
3 the set is 1 2 3 4 5, still giving 2.
## What most people try first
Sorting the prefix after every arrival. That is O(n log n) per line and
O(n^2 log n) overall, which at n = 200000 is about 7 * 10^11 steps.
Keeping the prefix sorted with an insertion. Better, and still O(n) per
arrival because inserting into the middle of an array shifts the tail. That is
2 * 10^10 element moves at the limits. This is exactly the weakness that
never appeared in problem 879: there the collection was fixed, here it grows
after every single question.
## A max-heap of size k, holding the k smallest
Only the smallest k values can ever matter, and among those the one being
asked for is the LARGEST. So hold the k smallest seen so far in a MAX-heap,
and its top is the answer.
That is problem 880 with every direction reversed, and setting them side by side is the fastest way to stop getting the direction wrong:
k largest -> keep them in a MIN-heap, the top is the worst survivor
k smallest -> keep them in a MAX-heap, the top is the worst survivor
In both cases the top is the item to evict. The difference here is that the
top is also the answer, which is a happy accident of asking for the kth
rather than the whole list.
h = empty max-heap
for each arriving v:
if size(h) < k: push v
else if v < top(h): pop, then push v
print top(h) if size(h) == k else "none"
## Why the top really is the kth smallest
By induction the heap holds exactly the k smallest values of the prefix.
The kth smallest of a set is the largest element of its k smallest, and
the largest element of a max-heap is its root. So one read answers the
question, in constant time, after an O(log k) update.
## The boundary that breaks a careless implementation
The first k - 1 lines. The heap is not yet full and there is no kth
value, so the line is none and the heap must NOT be consulted. A program
that prints the top regardless reports the largest of a partial set, which is
wrong and looks plausible.
The second one is k = n, where the first n - 1 lines are all none and
only the last line carries a number. The test with four values and k = 4 is
that case.
## What is NOT an overflow here
Nothing is summed, multiplied or accumulated. Values reach 10^9 in
magnitude and 10^9 sits comfortably inside the signed 32-bit range, whose
top is 2147483647. Problem 883 asks the same kind of question and does sum,
which is where the 32-bit build finally breaks.
## Related problems
Problem 243 asks the same rank of a FIXED array, where sorting is the answer. Problem 870 prints the running MEDIAN, which is not a fixed rank at all: the rank it wants moves as the count grows, and that is why it needs two heaps where this needs one. Problem 883 keeps the same heap but reports a total.
## Cost
Time O(n log k). Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers in arrival order.
Output
Print n lines, one per arrival: the kth smallest value among everything that has arrived so far, or the word none if fewer than k values have arrived.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.