2260. The Gap Around 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 gap x print how wide the hole around x is: the smallest stored key STRICTLY above x minus the largest stored key STRICTLY below x. Print none if either of those does not exist.

Note that x itself is excluded on both sides, so a stored x does not make the gap zero.

add 10 add 3 gap 5 -> 7 10 - 3 gap 3 -> none nothing is strictly below 3 gap 10 -> none nothing is strictly above 10 gap 11 -> none

## What most people try first

Scanning the collection for the nearest key on each side, which is O(m) per query and O(q^2) overall: 200000 operations is up to 4 * 10^10 comparisons.

The more interesting wrong answer is to keep a running "smallest gap so far" and update it on insertion. That answers a different and genuinely useful question, "how close are the two closest keys anywhere", and it cannot answer this one, because the gap at a particular x depends on which keys are currently nearest to x and a global minimum has thrown that away. Deletions make it worse: a running minimum cannot be undone when the pair that achieved it is broken up.

## Two candidates, and only two

Problem 2229 makes the same observation about the nearest key: out of every stored key, only two can possibly matter, the largest one below and the smallest one above. Here BOTH of them are wanted rather than the better of the two, so the structure of the solution is identical and nothing is thrown away at the end.

The two queries a Fenwick tree of counts can answer directly are "how many stored keys are below this value" and "which key sits at this rank". Everything in this pattern is one of each, composed:

count a prefix -> a rank descend for a rank -> a key

The prefix count is one binary search over the sorted distinct values followed by one Fenwick walk; the descent is one walk down the same tree. Both are O(log q).

## 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.

cl = the number of stored copies STRICTLY below x ch = the number of stored copies AT MOST x if cl == 0 or ch == m -> none lo = the clth smallest copy (one descent) hi = the (ch + 1)th smallest copy (one descent) print hi - lo

## Why those two ranks are the two neighbours

The copies strictly below x are ranks 1 .. cl, so the largest of them is rank cl. The copies at most x are ranks 1 .. ch, so the first copy strictly above x is rank ch + 1. The two counts use DIFFERENT comparisons on purpose, one strict and one not, and that is what excludes x itself from both sides. Using the same comparison twice makes a stored x count as its own neighbour and the gap come out too small.

## Overflow, checked rather than assumed

hi and lo are each at most 10^9 in magnitude and hi > lo, so the difference hi - lo is at most 2 * 10^9. The signed 32 bit maximum is 2147483647, so that fits, with about 147 million to spare, and this problem does not need 64 bit arithmetic for the answer. It is worth doing the subtraction rather than reaching for a wider type by reflex, because the margin here is genuinely thin and the next problem along may not have it.

## The boundary that breaks a careless implementation

Either side missing. Both guards are needed and they are different: cl == 0 for the lower side and ch == m for the upper. An implementation that checks only one of them prints a difference against a key that does not exist, and with an unguarded descent that key is whichever end of the tree the walk fell off.

## Cost

O(q log q) time and O(q) memory: two prefix counts and two descents per query.

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