1957. Is Anything At Exactly This Frequency

A collection of values changes, and the question is not about any particular value but about the SHAPE of the collection: is there some value that appears exactly f times?

add x add one copy of x remove x remove one copy of x freq x how many copies of x are present hasfreq f is there any value present exactly f times

## 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 no copy of x was present, in
• which case nothing changes.
• freq x prints x's count, which is 0 for a value that is absent.
• hasfreq f prints yes or no.

hasfreq 0 always prints no. A value with zero copies is not present, so there is nothing at frequency zero to find, and the alternative reading, that every value never added sits at frequency zero, would make the answer yes forever. That is settled here rather than left to the reader.

hasfreq 1 -> no add 7 -> 1 hasfreq 1 -> yes add 7 -> 2 hasfreq 1 -> no 7 has moved to frequency 2 and left frequency 1 empty hasfreq 2 -> yes freq 7 -> 2 remove 7 -> 1 hasfreq 1 -> yes

## What most people try first

A map from value to count, with hasfreq scanning the counts. It is correct and O(number of distinct values) per query, which is the same trap as in problem 1956 and costs about 4 * 10^10 comparisons at the stated limits.

The more interesting wrong idea is to keep a set of the frequencies in use. The problem is leaving: when 7 moves from frequency 1 to frequency 2, frequency 1 must become empty ONLY IF nothing else sits there. A set of frequencies cannot tell, so it either reports frequency 1 as occupied forever or removes it while another value still has one copy.

## A count of counts

Keep a second table indexed by FREQUENCY rather than by value, holding how many distinct values sit at that frequency.

``` cnt[x] copies of value x ofc[f] how many distinct values have exactly f copies

add x: if cnt[x] > 0: ofc[cnt[x]] -= 1 leave the old bucket cnt[x] += 1 ; ofc[cnt[x]] += 1 join the new one remove x: ofc[cnt[x]] -= 1 cnt[x] -= 1 if cnt[x] > 0: ofc[cnt[x]] += 1 a count of 0 joins nothing hasfreq f: ofc[f] > 0 ```

Every count change is two adjustments to ofc, one leaving and one joining, which is what makes the frequency table exact rather than approximate.

## Why it is correct

The invariant is that ofc[f] equals the number of distinct values x with cnt[x] = f, for every f at least 1.

Each operation changes exactly one value's count, by one. The leave-then-join pair is precisely the two entries of ofc that the invariant requires to change, and no other entry can be affected, because no other value's count moved. The guards handle the two ends: a value arriving from zero has no old bucket to leave, and a value falling to zero has no new bucket to join.

So the invariant is maintained exactly, and hasfreq f is a single lookup.

## The boundary that breaks a careless implementation

Joining the new bucket without leaving the old one. Frequency 1 then reports yes forever after the first value ever passes through it, and no test in which every value stays at the same count can detect it.

The second is a count of zero joining bucket zero. hasfreq 0 then starts answering yes as soon as anything is fully removed, which contradicts the rule above.

The third is hasfreq f for an f larger than any possible count. With q operations no value can appear more than q times, so the table only needs q entries and a larger f must answer no rather than read past the end of the array.

## Overflow

A value reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. Counts and frequencies are bounded by q, so at most 200000. Nothing is multiplied, and the frequency table is indexed rather than summed, so no intermediate grows.

## Cost

O(1) expected per operation, with O(number of distinct values + 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(1)` expected - 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