2242. Where a Key Ranks

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 rank v print 1 plus the number of stored keys strictly below v

That definition is deliberate: it is the position v would occupy if it were inserted ahead of every copy equal to it, counting from 1. It is defined whether or not v is stored, and it does not depend on how many copies of v there are.

add 10 add 3 rank 3 -> 1 no stored key is below 3 rank 10 -> 2 one stored key, the 3, is below 10 rank 11 -> 3 both are below 11 rank 2 -> 1

## What most people try first

Counting on every query. Walking the collection and comparing each key is O(m) per query, so 200000 operations is up to 4 * 10^10 comparisons. A sorted array with a binary search fixes the QUERY and not the UPDATES: putting a value into the middle of a sorted array moves everything after it, which is O(q) per update.

Problem 241 is the version where the sorted array is exactly right, because there the array is given once and never changes. Here the updates are interleaved with the queries.

## Rank is not an index, and the difference is duplicates

An index points at a slot. A rank counts keys. With 2, 2, 2 stored, rank 2 is 1 because nothing is strictly below 2, while the three copies occupy indexes 0, 1 and 2. Ask instead for the number of keys at most v and the same collection answers 3. Both are useful and they are not the same question, which is why this statement pins down which one it wants.

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

rank(v) = 1 + prefix sum of counts over every position whose value is < v

The boundary position comes from one binary search over the sorted distinct values, using a STRICT comparison, and the prefix sum is one Fenwick walk.

## Why it is correct

The compressed positions run in increasing value order, so the stored keys strictly below v are exactly those at positions before the boundary, with nothing in between and nothing left out. Summing the counts over that prefix therefore counts copies rather than distinct values, which is what the definition asks for. Using a non-strict comparison instead includes the copies of v itself, which is right for a different question and wrong for this one.

## 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 a rank is at most q + 1, so nothing here needs 64 bits.

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