1937. Putting the Array Back the Way It Was

An array of n entries starts out all zero. Four 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 rollback s put the array back the way it was at snapshot s get i print the current value at position i

n = 2 set 1 5 -> snap -> 1 snapshot 1 is 5 0 set 1 9 -> set 2 7 -> snap -> 2 snapshot 2 is 9 7 set 1 1 -> rollback 1 -> ok the array is 5 0 again, and snapshot 2 is gone get 1 -> 5 get 2 -> 0 snap -> 2 the next snapshot is numbered 2 again

## The rules, stated so the answer is decidable

• set prints nothing. The other three each print one line.
• set with a position outside 1..n changes nothing and prints nothing.
• snap gives the new snapshot the next id, counting from 1.
• rollback s restores the array exactly as it was at snapshot s, and
• DISCARDS every snapshot with an id above s. The next snap therefore gets
• the id s + 1, reusing a number that was used before. That is the rule that
• makes this a different problem from problem 1936, and it is the reason the
• answer cannot be a history list indexed by version.
• rollback 0 is legal and means the initial all-zero state, discarding every
• snapshot.
• rollback s where s is the id of the newest surviving snapshot is legal and
• undoes the writes made since it, keeping that snapshot.
• rollback s prints oor and changes nothing if s is below 0 or above the
• number of snapshots that currently survive.
• get i prints oor if i is outside 1..n.

Problem 1936 reads the past and never alters it, which is why one history list per position works there. Here the present can be moved backwards, so a version number can be handed out twice and a list indexed by version stops being well defined. The structure that does work is the one a database uses.

## What most people try first

Copy the array on every snap and copy one back on a rollback. Correct, and O(n) per snapshot in time and memory: with n and the snapshot count both at 10^5 that is 10^10 words.

The next instinct is to reuse problem 1936's history list, binary searching for the largest version at or below the current one. That is fast and WRONG, for a reason worth seeing. After rollback s the counter goes back to s, so a later snap mints s + 1 again. Entries recorded under the old s + 1, which were rolled back and should be invisible, are now at or below the current version again, and they come back to life on any position the rollback did not subsequently overwrite. Version numbers only work as history keys if they are never reused.

## Write down what you destroyed

a[1..n] the array as it stands now log a list of (position, previous value), one per successful set marks[s] the LENGTH of the log at the moment snapshot s was taken

set i v: log.append((i, a[i])); a[i] = v snap: marks.append(log.length); print the new id rollback s: while log.length > marks[s]: (i, old) = log.pop(); a[i] = old discard marks above s; print "ok" get i: print a[i]

## Why it is correct

The log is an exact record of the array's history in the only form that matters for going backwards: each entry says what one position held before one write. Undoing the writes in REVERSE order therefore restores the array exactly, and the reverse order is essential, because two writes to the same position leave two entries and replaying them forwards would restore the newer value.

marks[s] is the log length when snapshot s was taken, so every entry beyond that point describes a write made after snapshot s. Popping down to marks[s] undoes precisely the writes made after s and no others, which is the definition of restoring that snapshot. The marks above s are discarded because the writes they pointed into no longer exist.

Reading is the easy part here, and that is the trade: get is a single array access because a always holds the present, unlike problem 1936 where reading the present costs a binary search too.

## Why the undo loop is affordable

A rollback can pop many entries, so no single operation is constant time. But an entry is appended by exactly one set and popped at most once, after which it is gone for good, so the total popping across the entire run is bounded by the number of set operations. Every operation is amortised O(1), and the memory is O(q) rather than O(n) per snapshot.

Note what this costs: once rolled back, the discarded states are unreachable. This structure can go backwards but not forwards again, which is enough for a rollback and not enough for a redo. Problem 1936 can reach any snapshot but cannot change the past. Picking the structure is picking which of those two you need.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647, and are never summed. The log length and the snapshot count stay under 2 * 10^5. Nothing here needs 64 bit arithmetic, though n times the snapshot count is 4 * 10^10, which is exactly the number the copying approach would have to allocate and does not fit in 32 bits.

## Cost

Amortised O(1) per operation, O(q) total, with O(n + 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 - each of the four operations must run in amortised `O(1)`, so the whole run is `O(q)`, with `O(n + q)` memory rather than `O(n)` per snapshot - the judge cannot enforce that: 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 at the stated limits