1939. A Stack Whose Past Survives Its Pops

A stack starts empty. Five operations arrive, one per line:

push v put v on top pop remove the top value and print it snap take a snapshot and print the id it was given top s print the top value as it was at snapshot s size s print the height as it was at snapshot s

8 push 1 -> push 2 -> snap -> 1 snapshot 1 is 1 2 pop -> 2 snap -> 2 snapshot 2 is 1 top 1 -> 2 snapshot 1 still has its top, though it was popped size 1 -> 2 size 2 -> 1

## The rules, stated so the answer is decidable

• push prints nothing. The other four each print one line.
• pop on an empty stack prints empty and changes nothing.
• top s prints the top value at snapshot s, or empty if the stack was
• empty at that snapshot.
• top 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 as the stream
• runs.
• A snapshot is NOT undone by anything. A value popped after snapshot s is
• still the top of snapshot s, which is the whole point.

## What most people try first

Copy the whole stack on every snap. Correct, O(height) per snapshot: at 10^5 pushes and 10^5 snapshots that is 10^10 values stored.

The cheap-looking alternative is to record only the HEIGHT at each snapshot and read the live stack at that depth. That works as long as nothing is ever popped, and gives wrong answers the moment something is, because a popped value is gone from the live array while the snapshot that was taken before the pop still contains it. It is also wrong in the other direction: after enough pops the recorded height can exceed the live height entirely.

## Build the stack out of nodes nobody owns

Represent the stack as a chain of nodes, each holding a value and a link to the node beneath it, and keep one pointer to the top:

val[nd] the value at node nd par[nd] the node beneath it, with 0 meaning the floor dep[nd] its height, so dep[0] = 0 and dep[nd] = dep[par[nd]] + 1 cur the node the live top sits on

push v: make a new node with par = cur, dep = dep[cur] + 1; cur = it pop: print val[cur]; cur = par[cur] snap: remember cur under the next id top s: val[ the node snapshot s remembers ] size s: dep[ the node snapshot s remembers ]

No node is ever modified or freed.

## Why this makes snapshots free

A pop does not delete anything. It moves cur down one link, and the node it left behind still holds its value and still links to the node below it, so that node is a complete and valid stack all by itself. Every node in the structure is simultaneously the top of exactly one stack: its own chain down to the floor.

So a snapshot does not have to copy anything. It records which node was the top at that moment, and that single number is the entire snapshot. Nothing can invalidate it, because nothing is ever changed.

Keeping dep on each node is what makes size s constant rather than a walk: the height is fixed when the node is created and never changes, exactly like the value.

## Why it is correct

Two claims. First, each node's chain is the stack as it stood when that node was pushed, by induction: the new node's parent is the then-current top, so its chain is the old stack with the new value on top. Second, the live stack is the chain from cur, which the two operations maintain: a push makes a longer chain whose tail is the old one, and a pop returns to the chain's own tail.

Together those give the result: snapshot s remembers the node that was cur at that instant, that node's chain is the stack at that instant, and nothing later can alter it.

## What this costs

Memory is O(q), one node per push, and nodes are never reclaimed. That is the price, and it is the right one here: copying would be O(height) per snapshot, which is unboundedly worse. This is the same shape of trade as problem 1936, reached by a different route: there the sharing had to be arranged with a history list per position, and here the structure is already shared because a linked stack never rewrites a node.

A stack snapshotted this way can also be RESUMED rather than only read: setting cur back to a snapshot's node would carry on from there, which problem 1937 achieves with an undo log and much more work. The difference is that an array rewrites cells in place while a linked stack never does.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647, and are never summed. Node indices, depths and snapshot ids all stay under 2 * 10^5. Nothing here needs 64 bit arithmetic.

## Cost

O(1) per operation, O(q) memory.

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