2244. How Many Different 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 uniq a b print how many DIFFERENT stored keys lie in [a, b]

Different means copies do not count: with 10, 3 and another 10 stored, uniq 3 10 is 2, not 3. If a > b the answer is 0.

add 10 add 3 add 10 uniq 3 10 -> 2 uniq 4 10 -> 1 uniq 11 20 -> 0

## What most people try first

The count tree from problem 2243, which answers 3 on the example above because it counts copies. There is no arithmetic on those counts that recovers the number of different keys: a prefix sum of 2 could be one value with two copies or two values with one each, and the tree has thrown away which.

The second instinct is a separate sorted list of the distinct keys, with two binary searches per query. The query is then fast and every update costs O(q) to insert into or remove from the middle of the list, so 200000 operations is up to 2 * 10^10 element moves.

## The method: a second tree that holds presence, not population

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 TWO Fenwick trees over the same compressed positions:

TREE[i] how many copies of value i are stored PTREE[i] 1 when value i has at least one copy stored, 0 otherwise

PTREE is maintained by the SAME insert and delete, and it changes at only two moments:

add v -> if the count at v was 0 before this copy arrived, add 1 at v del v -> if the count at v reaches 0 as this copy leaves, subtract 1 at v

Then

uniq(a, b) = prefixSum(PTREE, values <= b) - prefixSum(PTREE, values < a)

with the same strict and non-strict pair of bounds a closed range always needs.

## Why maintaining it at the crossings is enough

The invariant to keep is "PTREE holds 1 exactly where the multiplicity is positive". A multiplicity only ever moves by one copy at a time, so it can cross zero only when the first copy arrives and when the last one leaves. Updating PTREE at precisely those two crossings therefore preserves the invariant with no rescanning, and once the invariant holds a prefix sum of PTREE is a count of different keys by construction.

## The boundary that breaks a careless implementation

Deleting one copy of a value that has two. The distinct count must not move until the second copy goes, and an implementation that subtracts from PTREE on every del drops it one delete early. The mirror image is adding on every add, which counts a repeated value twice. Both bugs are invisible on a stream with no duplicates, so the declared tests put two copies of one value in and take them out one at a time.

## 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 the distinct count is at most q = 200000.

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