Versioned Integer Array with Snapshots and Point-in-Time Reads

Build a fixed-length array of integers that remembers its history. Every element starts at 0. You can change elements, take numbered snapshots of the whole array, and later ask what value any element had at the moment a given snapshot was taken.

Because the grader calls a single function, the operations are supplied as a list and processed in order.

Function Signature

def run_snapshot_array(length: int, ops: List[str], args: List[List[int]]) -> List[int]:

Rules

• ops[i] names the i-th operation and args[i] holds its arguments:
• "set" with args[i] = [index, value] assigns value to position index of the live (current) array. It produces no output.
• "snap" with args[i] = [] records a snapshot of the live array and outputs its snapshot id. Ids count up from 0: the first snapshot is 0, the second is 1, and so on.
• "get" with args[i] = [index, snap_id] outputs the value that position index held when snapshot snap_id was taken.
• A snapshot reflects every "set" that came before it and none that came after it. If an index is set several times between two snapshots, the later snapshot sees only the last of those values.
• A position that was never set before a snapshot reads as 0 in that snapshot.
• Return a single list holding the outputs of every "snap" and every "get", in the order the operations appear. The result is fully determined by the input.

Constraints

• 1 <= length <= 5 * 10^4
• 1 <= len(ops) == len(args) <= 5 * 10^4
• Each ops[i] is one of "set", "snap", "get".
• For "set": 0 <= index < length and 0 <= value <= 10^9.
• For "get": 0 <= index < length and 0 <= snap_id < s, where s is the number of "snap" operations that appear before this "get".

Examples

Example 1

Input: length = 3
 ops = ["set", "snap", "set", "get"]
 args = [[0, 5], [], [0, 6], [0, 0]]
Output: [0, 5]

Position 0 holds 5 when snapshot 0 is taken. The later change to 6 does not affect snapshot 0.

Example 2

Input: length = 2
 ops = ["snap", "snap", "get", "set", "get", "snap", "get", "get"]
 args = [[], [], [1, 1], [1, 4], [1, 1], [], [1, 2], [0, 2]]
Output: [0, 1, 0, 0, 2, 4, 0]

Snapshots 0 and 1 are taken before any change, so position 1 reads 0 in snapshot 1 both before and after it is set to 4. Snapshot 2 sees the 4, and position 0 was never set.

Example 3

Input: length = 1
 ops = ["set", "set", "snap", "set", "get"]
 args = [[0, 3], [0, 7], [], [0, 9], [0, 0]]
Output: [0, 7]

Only the last value set before snapshot 0 counts, and the set to 9 happens after it.