1936. An Array You Can Read As It Used to Be

An array of n entries starts out all zero. Three operations arrive, one per line:

set i v write v at position i, 1-indexed snap take a snapshot and print the id it was given get i s print what position i held at snapshot s

Snapshot ids start at 1 and go up by one each time.

n = 3 set 1 5 -> snap -> 1 snapshot 1 is 5 0 0 set 2 7 -> set 1 9 -> snap -> 2 snapshot 2 is 9 7 0 get 1 1 -> 5 get 1 2 -> 9 get 3 1 -> 0 position 3 was never written get 1 3 -> oor there is no snapshot 3

## The rules, stated so the answer is decidable

• set prints nothing. snap and get each print one line.
• A snapshot records the array as it stands at that instant. Writes made AFTER
• snapshot s are not visible at s, including writes made before snapshot
• s + 1.
• A position never written reads as 0 at every snapshot.
• get i s prints oor if i is below 1 or above n, or if s is below 1 or
• above the number of snapshots taken so far. Note that this depends on when
• the get happens: a snapshot id that is out of range now may be in range
• later.
• Several set operations may land between two snapshots, in which case only
• the last one is visible at the next snapshot. That is the case that decides
• how the history is stored.

Problem 1916 also reads a value as it used to be, and the differences matter. There the TIMES come from the input and each key's times strictly increase, so one write is one recorded version. Here the versions are minted by the structure, all positions share one counter, and several writes can land inside a single version while others produce no version at all.

## What most people try first

Copy the whole array on every snap. That answers every get in one step and costs O(n) per snapshot: with n and the number of snapshots both at 10^5, that is 10^10 cells copied and 10^10 words of memory, which is hopeless in both directions. It is also the natural reading of the word snapshot, which is why it has to be named before it is replaced.

The mirror image is to keep a log of every write and replay the log from the start on every get. That uses O(q) memory and O(q) time per read, so a stream of 10^5 writes followed by 10^5 reads does about 10^10 steps.

## Keep one history per position, not one copy per snapshot

A snapshot does not need to record the whole array, because most positions did not change. What has to be recorded is, for each position, the versions at which its value changed.

hist[i] a list of (snapshots taken at the time of the write, value) snaps how many snapshots have been taken

A set i v appends (snaps, v) to hist[i], EXCEPT when the last entry already records snaps, in which case it overwrites that entry instead. So hist[i] has strictly increasing version numbers and holds at most one entry per version.

A snap costs nothing but incrementing the counter.

A get i s wants the last write that happened before snapshot s was taken. A write recorded with snaps = w happened when w snapshots existed, so it is visible at snapshot s exactly when w <= s - 1. Binary search hist[i] for the largest recorded version that is at most s - 1, and print its value, or 0 if there is none.

## Why it is correct

The recorded number w is the count of snapshots that existed when the write happened, so the write landed strictly between snapshot w and snapshot w + 1. It is therefore visible at every snapshot with id w + 1 or higher, and at none below. "Visible at s" is thus exactly w + 1 <= s, which is w <= s - 1. Using w <= s instead makes a write made immediately after snapshot s appear inside it, which is the single most common bug here and is why the declared tests include that exact stream.

Overwriting the last entry when it shares the current version is what keeps the version numbers strictly increasing, and a strictly increasing key is what makes the binary search well defined. Without it two entries could share a version and the search could return either, which is an unpinned answer rather than a slow one.

## Why it is fast, and small

Each set adds at most one entry, so the total memory across all positions is O(q) regardless of n. snap is O(1). get is O(log q). Nothing is ever copied.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647, and are never summed. Positions, snapshot ids and version numbers all stay under 2 * 10^5. Do not compute a flat offset as i * snaps: at the stated limits that product reaches 4 * 10^10, which does not fit in 32 bits, and it is the wrong structure anyway.

## Cost

O(1) per set and snap, O(log q) per get, O(q) memory.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ i ≤ 200001` - `0 ≤ v ≤ 1000000000` - `0 ≤ s ≤ 200001` - every position starts at 0 and no snapshot exists at the start - `set` and `snap` must run in `O(1)` and `get` in `O(log q)`, with `O(q)` memory in total rather than `O(n)` per snapshot - the judge cannot enforce either bound: the declared tests are small and there is no test generator yet, so copying the array on every snapshot passes them while using about `10^10` words of memory at the stated limits