2258. The Largest Key Strictly Below x

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 prev x print the largest stored key STRICTLY less than x, or none

add 10 add 3 prev 10 -> 3 10 itself does not count prev 3 -> none prev 11 -> 10 prev 2 -> none

## Strictly below, and why that is a different problem from 2226 and 357

Problem 2226 asks for the largest stored key at most x, the FLOOR. This asks for the largest strictly below x, the PREDECESSOR. They differ exactly when x is stored: with 3 and 10 stored, the floor of 10 is 10 and the predecessor of 10 is 3.

Problem 357 asks the predecessor question too, and asks it ONCE, of a binary search tree that is given fully built and never changes. What makes this different is that the collection changes between the queries, so there is no fixed tree to walk.

## What most people try first

A sorted array with a binary search, which is right for the query and O(q) per update, because an insertion or a deletion in the middle shifts the whole tail. Across 200000 operations that is up to 2 * 10^10 element moves.

The other instinct is to take the floor and then step back one if it equals x. That IS correct, and it is worth seeing why it is more work than it looks: the step back is another descent, and it has to handle the case where x has several copies, so the step is not one position but the whole run of copies. Counting strictly is simpler and costs one query rather than two.

## The method

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Compress them and keep a Fenwick tree of how many copies of each compressed value are stored.

c = the number of stored copies STRICTLY LESS than x (strict prefix count) if c == 0 -> none, nothing is below x answer = the cth smallest stored key (one binary descent)

## Why the strict count is the one that gives a strict predecessor

The copies strictly below x occupy ranks 1 .. c and are all eligible, so the largest of them is the one at rank c. Using the non-strict count instead would include the copies of x itself, and rank c would then be a copy of x, which is the floor. The pairing is the mirror of problem 2257: the strict PREDECESSOR uses a strict count, and the strict SUCCESSOR uses a non-strict one.

## The boundary that breaks a careless implementation

x at or below every stored key, which must print none. The guard is c == 0, and a descent for rank 0 is not a valid rank: unguarded, it returns the smallest stored key, which is above x and so plainly wrong, yet looks like an answer. Duplicates matter too: with three copies of 2 stored, prev 2 is none and prev 3 is 2, and an implementation that steps back one POSITION from the floor lands on another copy of 2 and reports it as the predecessor of 2.

## Cost

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