2243. How Many Keys Fall in a Range

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 cnt a b print how many stored keys lie in the closed range [a, b]

Copies count, so three copies of 5 contribute 3. If a > b the range is empty and the answer is 0. Neither a nor b need be stored.

add 10 add 3 cnt 3 10 -> 2 cnt 4 9 -> 0 cnt 10 10 -> 1 cnt 11 20 -> 0

## Why this is not problem 275 again

Problem 275 answers the same question on an array that is given once and never changes, which is why it is solved with two binary searches and nothing else. That whole approach rests on the array staying sorted for free. Here add and del are interleaved with the queries, so maintaining the sorted array costs O(q) per update, and 200000 operations is up to 2 * 10^10 element moves.

## What most people try first

Counting on every query, which is O(m) per query and O(q^2) overall. The second instinct, after reaching for a Fenwick tree, is to index it by VALUE. With values up to 10^9 in magnitude that is an array of two billion entries, which is roughly 8 gigabytes before anything has been stored.

## The method: compression turns a value range into an index range

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Sort the distinct values, give each one a position in that sorted list, and keep a Fenwick tree of counts over those positions. The tree is then O(q) wide no matter how large the values are. For a query,

hiBound = the number of distinct values that are <= b (non-strict) loBound = the number of distinct values that are < a (strict) answer = prefixSum(hiBound) - prefixSum(loBound)

Both bounds are one binary search over the sorted distinct values.

## Why the two comparisons must differ

The range is CLOSED at both ends, so a stored b is inside it and a stored a is inside it too. The upper bound therefore counts values at most b, and the subtracted lower part must count only values strictly below a. Using the same comparison at both ends is the classic failure here: with < at both ends a stored copy of b is dropped, and with <= at both ends a stored copy of a is dropped. Either bug is invisible on a test whose endpoints are not stored, which is why the declared cases include cnt 10 10 and cnt 2 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; the counts are at most q = 200000, and the difference of two prefix sums cannot exceed that.

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