Snapshot Array

class SnapshotArray {
    int snapId = 0;
    vector<vector<pair<int,int>>> data; // data[i] = sorted list of (snapId, val)
public:
    SnapshotArray(int length) : data(length, vector<pair<int,int>>{{0, 0}}) {}

    void set(int index, int val) {
        auto& v = data[index];
        if (v.back().first == snapId) v.back().second = val;
        else v.push_back({snapId, val});
    }

    int snap() { return snapId++; }

    int get(int index, int snap_id) {
        auto& v = data[index];
        int lo = 0, hi = (int)v.size() - 1, ans = 0;
        while (lo <= hi) {
            int m = (lo + hi) / 2;
            if (v[m].first <= snap_id) { ans = m; lo = m + 1; }
            else hi = m - 1;
        }
        return v[ans].second;
    }
};

type SnapshotArray struct {
    snapId int
    data   [][][2]int // data[i] = list of (snapId, val)
}

func Constructor(length int) SnapshotArray {
    data := make([][][2]int, length)
    for i := range data {
        data[i] = [][2]int{{0, 0}}
    }
    return SnapshotArray{snapId: 0, data: data}
}

func (s *SnapshotArray) Set(index int, val int) {
    v := s.data[index]
    last := len(v) - 1
    if v[last][0] == s.snapId {
        s.data[index][last][1] = val
    } else {
        s.data[index] = append(v, [2]int{s.snapId, val})
    }
}

func (s *SnapshotArray) Snap() int {
    s.snapId++
    return s.snapId - 1
}

func (s *SnapshotArray) Get(index int, snap_id int) int {
    v := s.data[index]
    lo, hi, ans := 0, len(v)-1, 0
    for lo <= hi {
        m := (lo + hi) / 2
        if v[m][0] <= snap_id {
            ans = m
            lo = m + 1
        } else {
            hi = m - 1
        }
    }
    return v[ans][1]
}

from bisect import bisect_right
from typing import List, Tuple

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data: List[List[Tuple[int, int]]] = [[(0, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        v = self.data[index]
        if v[-1][0] == self.snap_id:
            v[-1] = (self.snap_id, val)
        else:
            v.append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        v = self.data[index]
        # find rightmost entry with first <= snap_id
        i = bisect_right(v, (snap_id, float('inf'))) - 1
        return v[i][1]

class SnapshotArray {
    constructor(length) {
        this.snapId = 0;
        this.data = Array.from({ length }, () => [[0, 0]]);
    }
    set(index, val) {
        const v = this.data[index];
        const last = v[v.length - 1];
        if (last[0] === this.snapId) last[1] = val;
        else v.push([this.snapId, val]);
    }
    snap() {
        return this.snapId++;
    }
    get(index, snap_id) {
        const v = this.data[index];
        let lo = 0, hi = v.length - 1, ans = 0;
        while (lo <= hi) {
            const m = (lo + hi) >> 1;
            if (v[m][0] <= snap_id) {
                ans = m;
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return v[ans][1];
    }
}

class SnapshotArray {
    private int snapId = 0;
    private List<List<int[]>> data;

    public SnapshotArray(int length) {
        data = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            List<int[]> v = new ArrayList<>();
            v.add(new int[]{0, 0});
            data.add(v);
        }
    }

    public void set(int index, int val) {
        List<int[]> v = data.get(index);
        int[] last = v.get(v.size() - 1);
        if (last[0] == snapId) last[1] = val;
        else v.add(new int[]{snapId, val});
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snap_id) {
        List<int[]> v = data.get(index);
        int lo = 0, hi = v.size() - 1, ans = 0;
        while (lo <= hi) {
            int m = (lo + hi) / 2;
            if (v.get(m)[0] <= snap_id) {
                ans = m;
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return v.get(ans)[1];
    }
}

class SnapshotArray {
    private snapId: number = 0;
    private data: [number, number][][];

    constructor(length: number) {
        this.data = Array.from({ length }, () => [[0, 0]]);
    }

    set(index: number, val: number): void {
        const v = this.data[index];
        const last = v[v.length - 1];
        if (last[0] === this.snapId) last[1] = val;
        else v.push([this.snapId, val]);
    }

    snap(): number {
        return this.snapId++;
    }

    get(index: number, snap_id: number): number {
        const v = this.data[index];
        let lo = 0, hi = v.length - 1, ans = 0;
        while (lo <= hi) {
            const m = (lo + hi) >> 1;
            if (v[m][0] <= snap_id) {
                ans = m;
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return v[ans][1];
    }
}