2257. The Smallest Key Strictly Above 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 next x print the smallest stored key STRICTLY greater than x, or none

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

## Strictly above, and why that is a different problem from 2227

Problem 2227 asks for the smallest stored key at least x, the CEILING. This asks for the smallest strictly above x, the SUCCESSOR. They differ exactly when x itself is stored: with 3 and 10 stored, the ceiling of 3 is 3 and the successor of 3 is 10.

That one word is the single most common source of a wrong answer in this whole topic, and it is invisible on any test whose query value is absent from the collection. Interviews name the two separately, lower_bound and upper_bound, for the same reason.

## What most people try first

A sorted array and a binary search. The search is right and the maintenance is not: inserting into or deleting from the middle of a sorted array shifts everything after it, which is O(q) per update and up to 2 * 10^10 element moves across 200000 operations.

A hash set cannot help at all, since it has no notion of which key comes next, and a heap gives only the extreme.

## 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, with m the number of stored copies.

c = the number of stored copies AT MOST x (non-strict prefix count) if c == m -> none, every stored key is at most x answer = the (c + 1)th smallest stored key (one binary descent)

## Why the non-strict count is the one that gives a strict successor

The copies at most x occupy ranks 1 .. c, so rank c + 1 is the first copy that is NOT at most x, which is to say the first one strictly greater. Using the strict count instead, c would exclude the copies of x itself, and rank c + 1 would then be a copy of x, which is the ceiling rather than the successor. So the strict query uses the non-strict count, and the ceiling query uses the strict one: the two comparisons swap over, which is why writing them from memory goes wrong.

## The boundary that breaks a careless implementation

x at or above every stored key, which must print none. The guard is c == m, and an unguarded descent for rank m + 1 walks to the end of the tree and returns the largest key. The declared tests include next 10 on a collection whose largest key is 10, and next 11 above everything.

## 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 `next x`. - Every value that can ever be stored appears in the input, so the values are known in advance.