1960. How Many Keys Are Above The Line

Keys are counted up and down, and the question is about the whole population at once: how many distinct keys are currently above a given threshold?

add x one more occurrence of x remove x one fewer occurrence of x count x how many occurrences of x are present above f how many distinct keys have strictly more than f occurrences

## What every operation prints

Every operation prints exactly one line.

• add x prints x's new count.
• remove x prints x's new count, or none if x was absent, in which case
• nothing changes.
• count x prints x's count, which is 0 for an absent key.
• above f prints how many distinct keys have a count STRICTLY greater than
• f. So above 0 is the number of keys present at all, and the threshold is
• exclusive at both readings: a key with exactly f occurrences is not counted.

A key whose count falls to 0 is no longer present, so it is not counted by above 0.

above 0 -> 0 add 1 -> 1 add 1 -> 2 add 2 -> 1 above 0 -> 2 keys 1 and 2 are present above 1 -> 1 only key 1 has more than one count 1 -> 2 remove 1 -> 1 above 1 -> 0 nothing has more than one any more

## This is not problem 1957

Problem 1957 asks whether anything sits at EXACTLY a frequency, which a table indexed by frequency answers with one lookup. This asks how many sit ABOVE a frequency, which is a sum over a whole range of that table. A sum over a range that keeps changing is a different problem, and a plain array cannot do both cheaply: maintaining running totals makes the update linear, and keeping raw counts makes the query linear.

## What most people try first

Scan every distinct key and compare its count with f. Correct, and O(D) per query.

The second idea is a suffix total array over frequencies, so above f is one read. The update then has to adjust every entry below the changed frequency, which is O(q) per update: the cost has moved rather than gone.

## A Fenwick tree over the frequencies

The structure that gives both a cheap point update and a cheap range sum is a Fenwick tree, indexed by frequency rather than by key.

``` cnt[x] occurrences of x FW a Fenwick tree where position f holds how many distinct keys have exactly f occurrences live how many distinct keys are present at all

add x: if cnt[x] > 0: FW.add(cnt[x], -1) leave the old frequency else: live += 1 cnt[x] += 1 ; FW.add(cnt[x], +1) join the new one remove x: FW.add(cnt[x], -1) cnt[x] -= 1 if cnt[x] > 0: FW.add(cnt[x], +1) else: live -= 1 above f: live - FW.prefixSum(f) ```

The answer is phrased as a subtraction on purpose. A Fenwick tree gives prefix sums cheaply and suffix sums awkwardly, and the number of keys above f is the number present minus the number at f or below. Keeping live separately turns the suffix question into a prefix one.

## Why it is correct

Two invariants. FW holds, at position f, the number of distinct keys with exactly f occurrences, maintained by the same leave-then-join pair as problem 1957. And live is the number of keys with a count of at least 1, changed only when a key arrives from zero or falls to zero.

Then FW.prefixSum(f) is the number of keys with between 1 and f occurrences, so live minus it is the number with more than f, which is what above f asks. Note that position 0 is never written, which is what keeps keys at count zero out of both terms.

## The boundary that breaks a careless implementation

Strict versus inclusive. above f excludes a key with exactly f occurrences, so the prefix sum runs up to and including f. Summing up to f - 1 instead counts the keys at f, and the two agree on every input where no key happens to sit exactly on the threshold.

The second is a key falling to zero. It must leave live as well as the tree, or every later above 0 is too high, and that only shows after something has been fully removed.

The third is a threshold larger than any possible count. With q operations no key appears more than q times, so a larger f must answer 0 rather than index past the tree.

## Overflow

A key reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. Counts, frequencies and the tree's totals are all bounded by q, so at most 200000. The Fenwick index arithmetic uses i & (-i), which is a bitwise operation: in JavaScript that truncates to 32 bits, and it is safe here only because the index is at most 200002. The TOTALS stored in the tree are never touched by a bitwise operator, which is what keeps them exact.

## 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` - `0 ≤ f ≤ 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