2227. The Smallest Key At Least x

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

add v put another copy of v into the collection ceil v print the smallest stored key that is at least v, or none

Print one line for every ceil.

add 10 ceil 10 -> 10 ceil 11 -> none add 30 ceil 11 -> 30

Problem 2226 asks for the largest key at most v. This asks for the smallest at least v, and the two are not mirror images in the code even though they are in the story.

## The complexity contract

add O(log q) ceil O(log q)

## Why the two are not the same expression

With a Fenwick tree of counts over compressed values, the floor came out of "how many keys are at most v" followed by one binary descent. The ceiling needs a different count:

floor(v): c = atMost(v); answer = the c-th smallest, none if c == 0 ceil(v): c = less(v); answer = the (c+1)-th smallest, none if c == total

The floor uses atMost, which counts keys <= v. The ceiling uses less, which counts keys < v. Using atMost for both is the error this problem exists to catch: on a collection holding v itself, atMost(v) already counts that copy, so (atMost(v) + 1)-th gives the key AFTER v rather than v.

The test add 7 then ceil 7 answers 7, and the wrong version answers none.

## Where the two counts come from

less and atMost are the lower and upper bounds of v in the compressed value list, turned into prefix sums:

less(v) = prefix( number of distinct values strictly below v ) atMost(v) = prefix( number of distinct values at most v )

Both are a binary search over the compressed list followed by one prefix sum. Note that the binary search is over the UNIVERSE, which never changes, while the prefix sum is over the current contents, which do.

## What most people try first

A sorted array with a binary search for the ceiling. The query is O(log q) and the insertion is O(q), and with q at 200000 the moves reach 2 * 10^10. Problem 241 is the version on a fixed array, where the array is exactly right.

## Why the values may be compressed

Every operation is read before the first is executed, so every value that can ever be stored is known in advance. That is what makes the Fenwick tree possible, and it is stated because it is a real restriction on the problem rather than a trick.

## Cost

O(q log q) and O(q) memory. A value of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and nothing here adds two values.

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