2226. The Largest Key At Most x

A collection of integers starts empty. Then q operations arrive, one per line:

add v put another copy of v into the collection floor v print the largest stored key that is at most v, or none

Print one line for every floor.

add 10 floor 10 -> 10 floor 9 -> none add 3 floor 9 -> 3

Note that v need not be stored. The question is about order, not membership.

## Why a hash set cannot answer this

A hash set answers "is v present" in constant time and nothing else. It has no notion of which key comes before another, so to find the largest key at most v it would have to look at every stored key. That is the difference between a hash structure and an ORDERED one, and it is the whole reason this topic exists separately from problem 286 and the hashing block.

A heap is no better. It gives you the extreme element and nothing in between, so the heaps block cannot answer a floor query either.

## The complexity contract

add O(log q) floor O(log q)

## What most people try first

An array kept in sorted order, with a binary search for the floor. The SEARCH is fine, O(log q), and the INSERT is not: putting a value in the middle of a sorted array moves everything after it, which is O(q) per operation. With q at 200000 that is up to 2 * 10^10 element moves.

Problem 262 is the version where that is the right answer, because there the array is given once and never changes. Here the updates are interleaved with the queries, which is exactly what makes the array lose.

## The values are known before anything is stored

Every operation is read before the first one is executed, so the set of values that can ever appear in the collection is known in advance. That makes it legal to COMPRESS them: sort the distinct values, and refer to each by its position in that sorted list.

The statement says this explicitly because it changes which structures are available. In particular it is what lets the C reference solution use a Fenwick tree of counts instead of a balanced tree, since C has no ordered set in its standard library.

## Floor from a Fenwick tree of counts

Keep an array cnt indexed by compressed value, holding how many copies of that value are stored, inside a Fenwick tree so that prefix sums are O(log q).

atMost(v) = the number of stored keys <= v = prefix sum up to the last compressed index whose value is <= v floor(v) = c = atMost(v); none if c == 0, otherwise the c-th smallest key

and the c-th smallest key comes out of one BINARY DESCENT of the same tree: walk down from the highest power of two, taking a step whenever the subtree count is still smaller than what remains.

## Why that is the right reduction

"The largest key at most v" and "the c-th smallest key" are the same question once c is known, because the keys at most v are exactly the first c in sorted order and the largest of them is the c-th. So one prefix sum and one descent answer the query, and the descent is the part a plain prefix-sum array cannot do.

## Cost

O(q log q) overall, with O(q) memory. A value fits in a signed 32 bit integer, since 10^9 is below 2147483647, and nothing here adds two values together.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - Every operation is `add v` or `floor v`. - Every value that can ever be stored appears in the input, so the values are known in advance.