2248. How Many Keys Are Within d

A collection of integers starts empty. 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 near v d print how many stored keys are within distance d of v

Within distance d means in the closed range [v - d, v + d]. Copies count, v need not be stored, and d may be 0, in which case the answer is the number of copies of v itself.

add 10 add 3 near 6 4 -> 2 the range is [2, 10] near 6 3 -> 1 the range is [3, 9] near 6 0 -> 0 the range is [6, 6] near 10 0 -> 1

## What most people try first

Scanning the collection and testing abs(x - v) <= d on every stored key. It is O(m) per query and O(q^2) overall, so 200000 operations is up to 4 * 10^10 comparisons. It is also the version that makes the overflow below invisible, because abs(x - v) never leaves the range of the values.

## 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, keep a Fenwick tree of how many copies of each compressed value are stored, and turn the distance condition into a range:

abs(x - v) <= d is the same as v - d <= x <= v + d answer = prefixCount(<= v + d) - prefixCount(< v - d)

Each bound is one binary search over the sorted distinct values, with the usual non-strict comparison at the top and strict at the bottom so that a closed range includes both its ends. Note that v - d and v + d need not be values that appear anywhere, which is fine: a binary search over the sorted distinct values answers "how many are at most this" for any number at all.

## Why the rewrite is exact

abs(x - v) <= d says x - v lies in [-d, d], and adding v to all three parts gives x in [v - d, v + d]. Both directions hold, so no key is counted that should not be and none is missed. The rewrite is what lets a structure that only knows about order answer a question phrased as a distance.

## Overflow, and why this one really bites

v reaches 10^9 in magnitude and d reaches 2 * 10^9, so v + d reaches 3 * 10^9 and v - d reaches -3 * 10^9. The signed 32 bit limit is 2147483647, so BOTH bounds leave the range of a 32 bit integer even though v and d each fit in one comfortably.

A 32 bit computation of v + d wraps round to a large negative number, and the upper bound then sits below the lower one, so the query confidently answers 0. That is a plausible answer, which is why it survives review. The declared tests include near 1000000000 2000000000, where the true answer is 1 and a 32 bit implementation prints 0.

Compute both bounds in 64 bit. The ANSWER is small, at most q = 200000; it is only the bounds that overflow.

## The boundary that breaks a careless implementation

d = 0. The range collapses to the single value v, and the answer is the number of copies of v, which is 0 when v is absent. An implementation that special-cases the empty range, or that uses the same comparison at both ends, gets this one wrong in both directions.

## Cost

O(q log q) time and O(q) memory.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - `0 ≤ d ≤ 2000000000` - A `del v` always names a value with at least one copy currently stored. - Every operation is `add v`, `del v` or `near v d`. - Every value that can ever be stored appears in the input, so the values are known in advance.