1938. A Set That Remembers Who Was In It

A set of integers starts empty. Five operations arrive, one per line:

add x put x in the set remove x take x out of the set snap take a snapshot and print the id it was given has x s print whether x was in the set at snapshot s size s print how many members the set had at snapshot s

7 add 3 -> add 5 -> snap -> 1 snapshot 1 holds {3, 5} remove 3 -> snap -> 2 snapshot 2 holds {5} has 3 1 -> yes size 2 -> 1

## The rules, stated so the answer is decidable

• add and remove print nothing. The other three each print one line.
• add of a value already in the set changes nothing. remove of a value not
• in the set changes nothing. Neither is an error, and neither affects any
• later answer, which matters because it decides whether a history entry should
• be recorded at all.
• A snapshot records the set as it stands at that instant. Changes made after
• snapshot s are not visible at s.
• has x s and size s print oor when s is below 1 or above the number of
• snapshots taken so far. As in problem 1936, that range grows, so the same
• query can be out of range early and valid later.
• A value never added reads no at every snapshot.

Problem 1936 is this idea applied to an array of values. Two things are new here. An operation can change nothing at all, which an array write never does. And size s is an aggregate over the WHOLE container at a past version, which cannot be answered from any one value's history.

## What most people try first

Copy the whole set on every snap. Every read is then trivial and the cost is O(size) per snapshot: with 10^5 members and 10^5 snapshots that is 10^10 values stored, so it fails on memory before it fails on time.

## Two different structures for two different questions

has x s is a question about one value, so give each value its own history:

hist[x] a list of (snapshots taken at the time, in or out)

An add or remove that CHANGES the membership appends (snaps, flag), or overwrites the last entry if it already records snaps. One that changes nothing records nothing at all. Then has x s is a binary search for the largest recorded version at most s - 1, answering yes when that entry says in, and no when there is no such entry, because the value was not a member before it was ever touched.

size s is a question about every value at once, so no per-value history can answer it. But the answer only has to exist at the instants snapshots are taken, and there are at most q of those, so keep a running member count and record it in an array at each snap. Then size s is one array read.

## Why it is correct

The version rule is the same as in problem 1936, and for the same reason: a change recorded when w snapshots existed happened between snapshot w and snapshot w + 1, so it is visible at snapshot s exactly when w <= s - 1.

Recording nothing for a no-op is not an optimisation, it is required for the overwrite rule to be sound. Consider add 3, snap, add 3. The second add changes nothing. If it recorded an entry at the new version, the history would carry a redundant entry, which is harmless here; but an implementation that records on every call usually also updates the running size on every call, and then the size is wrong. Deciding the no-op once, at the top, keeps the history and the count consistent with each other.

The running count is correct because it changes by exactly one on exactly the operations that change membership, which are the same operations that record history. The two structures therefore agree by construction rather than by coincidence.

## Overflow

Values are at most 2 * 10^5 so they index an array directly, which is why no hash map is needed. The member count and the snapshot count are both at most 2 * 10^5. Nothing here is summed or multiplied into a large number, so 32 bit arithmetic is safe throughout. A rectangular array of snapshots by values would be 4 * 10^10 cells, which does not fit in 32 bits and is the approach being avoided.

## Cost

O(1) per add, remove, snap and size, O(log q) per has, and O(q) memory.

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ x ≤ 200000` - `0 ≤ s ≤ 200001` - the set starts empty and no snapshot exists at the start - `add`, `remove`, `snap` and `size` must run in `O(1)` and `has` in `O(log q)`, with `O(q)` memory rather than one copy of the set per snapshot - the judge cannot enforce either bound: the declared tests are small and there is no test generator yet, so copying the set on every snapshot passes them while storing about `10^10` values at the stated limits