2262. The Next Key Around the Circle

A collection of integers starts empty and may hold several copies of the same value. The stored keys are treated as arranged in a CIRCLE: after the largest comes the smallest again. 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 cyc x print the smallest stored key strictly greater than x; if there is no such key, wrap round and print the smallest stored key of all. Print none only when nothing at all is stored.

add 10 add 3 cyc 3 -> 10 cyc 10 -> 3 nothing above 10, so wrap to the smallest cyc 2 -> 3 cyc 11 -> 3 wrap

## Why the wrap is the whole problem

Without it this is problem 2257. With it, the answer none means something completely different: in 2257 it means "nothing is above x", and here it means "nothing is stored at all". So the one natural place to return none has to be converted into a second query, and the one place that really is empty has to be detected separately. Getting this backwards gives a solution that prints none for every query above the largest key, which is correct for 2257 and wrong here, and no test whose queries all sit inside the range of stored keys will notice.

## What most people try first

A modulo. Round-robin scheduling by index is usually done with (i + 1) % n, and the reflex is to look for an arithmetic version of the wrap. There is none, because the keys are arbitrary integers rather than consecutive indexes: the key after the largest is not "the largest plus one modulo something", it is the smallest stored key, and only the structure knows what that is.

The second instinct, scanning for the smallest key greater than x and falling back to a scan for the global minimum, is correct and O(m) per query, so O(q^2) overall: 200000 operations is up to 4 * 10^10 comparisons.

## The method: at most two queries on one tree

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.

if m == 0 -> none cm = copies AT MOST x if cm < m -> rank cm + 1 the ordinary successor otherwise -> rank 1 the wrap, the smallest key

Both branches are one binary descent, and the two cases are told apart by a single comparison of the prefix count against m.

## Why the wrap is exactly rank 1

cm == m says every stored copy is at most x, so going round the circle from x the next key encountered is the smallest one, which is rank 1. Note this also covers x being equal to the largest key, and x being far above every key, with no separate case: both make cm == m. The empty collection has to be excluded first, because rank 1 does not exist there and an unguarded descent returns a position that holds nothing.

## The boundary that breaks a careless implementation

One stored key, queried at itself. The successor does not exist, so the wrap fires and the answer is that same key, which looks like a bug and is the definition. Three copies of one value behave the same way. The declared tests include both, because an implementation that refuses to return x itself passes everything else.

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