2230. The Value Filed Under the Floor Key

A table of key-and-value pairs starts empty. Keys are unique. Then q operations arrive, one per line:

put k val store val under key k, replacing whatever was there del k remove key k and its value; nothing happens if k is absent fval k print the value stored under the FLOOR of k, or none

The floor of k is the largest key present that is at most k. Print one line for every fval.

put 10 100 put 30 300 fval 20 -> 100 the floor of 20 is 10, whose value is 100 fval 10 -> 100 fval 5 -> none no key is at most 5

## The complexity contract

put O(log q) del O(log q) fval O(log q)

## Why this is a different structure from problems 2226 to 2229

Those keep a multiset: the thing stored IS the thing queried. Here the ordered structure holds the KEYS and a separate lookup holds the value filed under each one. That is the shape interviews mean by a sorted map rather than a sorted set, and it is also the shape a "what was the price at this time" question has.

Two consequences in the code. Keys are UNIQUE, so put on an existing key replaces the value and must NOT insert the key again, or every count in the ordered structure drifts. And fval is two steps rather than one: find the floor KEY by order, then read its value by lookup.

## What most people try first

A hash map from key to value. That answers fval k only when k is itself present, and the whole point is that it need not be: the floor of 20 is 10. A hash map has no notion of which key comes before another, so finding the floor would mean looking at every key.

The second instinct is a sorted array of keys alongside a parallel array of values. The query becomes O(log q) and both updates stay O(q), because an insertion or a deletion in the middle shifts both arrays.

## The method

Compress the keys, which the problem allows because every operation is read before the first one runs. Then

presence: a Fenwick tree of 0s and 1s indexed by compressed key values: a plain array indexed by compressed key put k val: if the key is absent, add 1 at its index; value[index] = val del k: if the key is present, add -1 at its index fval k: c = how many keys present are at most k none if c == 0, else read value at the index of the c-th smallest key

The value array is indexed by the COMPRESSED key, not by the order of insertion, which is what keeps it valid while keys come and go.

## Why a presence flag is needed beside the tree

put has to know whether the key is already present, and asking the Fenwick tree costs two prefix sums. A plain boolean array indexed by compressed key answers it in constant time and is the obvious companion structure. Without it the natural mistake is to add 1 unconditionally, which double counts the key and makes every later count, and therefore every floor, wrong.

The declared test put 5 50, put 5 55, fval 5 catches exactly that: the answer is 55 and the key must still be counted once.

## Cost

O(q log q) time and O(q) memory. Keys and values both fit in a signed 32 bit integer, since 10^9 is below 2147483647, and nothing here adds two of them together.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ k ≤ 1000000000` - `-1000000000 ≤ val ≤ 1000000000` - Every operation is `put k val`, `del k` or `fval k`. - Every key that can ever be stored appears in the input, so the keys are known in advance.