Snapshot Array
Implement a SnapshotArray that supports:
- set(index, val) - Set the element at index to val.
- snap() - Take a snapshot and return the snap_id (starts at 0, increments).
- get(index, snap_id) - Return the value at index for the given snap_id.
You will receive a sequence of operations. Output the result of each snap and get operation on a separate line.
Example
Input
3 set,0,5;snap;set,0,6;get,0,0
Output
0 5
Reasoning
- The input sequence starts with
set,0,5, setting the element at index 0 to 5. - The next operation is
snap, which takes a snapshot and returns the snap_id, starting at 0, so the output is0. - Then, the element at index 0 is updated to 6 with
set,0,6. - Finally,
get,0,0retrieves the value at index 0 for snap_id 0, which was 5 before the update, resulting in an output of5.
Constraints
- 1 <= length <= 50000
- 0 <= index < length
- 0 <= val <= 10^9
- At most 50000 total operations