1146. Snapshot Array

constructor O(1) set O(1) snap O(1) get O(logSnaps)
用这个

class SnapshotArray {
public:
    SnapshotArray(int length) {
        snaps.resize(length);
    }

    void set(int index, int val) {
        if (snaps[index].empty() || snaps[index].back().first != sid && snaps[index].back().second != val) { // 如果没有index的snap记录或者只有旧的记录（跟新值不同的），添加下一个snap_id的记录
            snaps[index].emplace_back(sid, val);
        } else {
            snaps[index].back().second = val; // 如果已经有下一个snap_id的记录则直接修改即可
        }
    }

    int snap() {
        return sid++;
    }

    int get(int index, int snap_id) {
        auto &v = snaps[index];
        auto it = upper_bound(begin(v), end(v), make_pair(snap_id, INT_MAX)); // 为了找到上界需要使用INT_MAX
        return it == begin(v) ? 0 : prev(it)->second; // 最开始所有元素都为0所以找不着就给0
    }

    vector<vector<pair<int, int>>> snaps; // key是index，pair是sid和val
    int sid = 0; // 下一个snap_id;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */