1963. How Many Keys Are Ahead Of This One

Keys carry counts that rise and fall. Given a key, how many other keys are ahead of it?

inc x raise key x's count by one dec x lower key x's count by one count x how many occurrences x has rank x how many distinct keys have strictly more occurrences than x

## What every operation prints

Every operation prints exactly one line.

• inc x prints x's new count.
• dec x prints x's new count, or none if x's count was already 0, in which
• case nothing changes.
• count x prints x's count, which is 0 for a key that is not present.
• rank x prints how many distinct keys have STRICTLY more occurrences than
• x, or none if x is not present at all. A key tied with x is not ahead
• of it, and x is never ahead of itself, so a key alone at the top has rank 0.

A key whose count reaches 0 stops existing, so it is neither ranked nor counted in anybody else's rank.

rank 1 -> none inc 1 -> 1 rank 1 -> 0 key 1 is the only key inc 2 -> 1 inc 2 -> 2 rank 1 -> 1 key 2 is ahead rank 2 -> 0 count 2 -> 2 dec 2 -> 1

## This is not problem 1960

Problem 1960 asks how many keys are above a threshold GIVEN in the operation. Here the threshold is the queried key's own count, which has to be looked up first and then used as the bound. The structure is the same; what changes is that the query is relative rather than absolute, so the answer to rank x moves when OTHER keys change even though x has not been touched.

That is worth sitting with, because it rules out caching a rank on the key.

## What most people try first

Scan every distinct key and compare counts. Correct, and O(D) per query, about 4 * 10^10 comparisons at the stated limits.

Caching a rank per key is the tempting repair and it is worse than slow: it is wrong. A single inc on one key changes the rank of every key below it, so a cache would have to be invalidated almost everywhere on every operation.

## A Fenwick tree over the counts

``` cnt[x] occurrences of key x FW position f holds how many distinct keys have exactly f occurrences live how many distinct keys are present

inc x / dec x: leave the old position, join the new one, keeping live in step when a key arrives from zero or falls to zero rank x: mine = cnt[x] if mine = 0: none otherwise: live - FW.prefixSum(mine) ```

FW.prefixSum(mine) counts every key with between 1 and mine occurrences, which includes x itself and every key tied with it. Subtracting that from live leaves exactly the keys strictly ahead, so the two parts of the rule, that ties do not count and that a key does not outrank itself, are both handled by the same inclusive prefix rather than by special cases.

## Why it is correct

The tree holds, at each position, the number of keys with exactly that many occurrences, maintained by the leave-then-join pair of problem 1957, and live counts keys with at least one occurrence. Position 0 is never written, so a key at zero is in neither term.

For a present key x with count m, the keys strictly ahead are those with count at least m + 1, and that set is live minus those with count between 1 and m, which is the inclusive prefix at m. Hence the formula, with no correction for x itself: x is already inside the prefix.

## The boundary that breaks a careless implementation

Using the prefix up to mine - 1, which leaves x and its ties outside the subtraction, so every answer is too high by at least one. Because the error is at least one on every query, it is caught by almost any test, which is the better kind of mistake.

The second is a key falling to 0. It must leave live, or it is counted as being ahead of keys it no longer competes with, and it must also make rank on itself print none.

The third is rank on a key never seen, which must print none rather than 0: rank 0 means alone at the top, which is a different statement.

## Overflow

A key reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. Counts, live and the tree's totals are all bounded by q, so at most 200000. The Fenwick step uses i & (-i), a bitwise operation, which in JavaScript truncates to 32 bits and is safe only because the index is a count of at most 200002; the stored totals are never passed through a bitwise operator.

## Cost

O(log q) per operation, with O(D + q) memory. the judge cannot enforce that: the declared tests are small and there is no test generator yet, so scanning every distinct key on each query passes them while doing about 4 * 10^10 comparisons at the stated limits.

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ x ≤ 1000000000` - every operation runs in `O(log q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so scanning every distinct key on each query passes them while doing about `4 * 10^10` comparisons at the stated limits