【面接問題】一つのデータ構造を実現するには、set(index,val)、get(index)、setAll(val)の3つの操作時間の複雑さがO(1)であることが要求されます.

class Node{
private:
    map<int, pair<int, int> > mp; // index, cnt, val
    int tot;
    int cnt = 0;
public:
    void set(int index, int value) {
        mp[index] = {cnt, value};
    }
    int get(int index) {
        int tcnt = mp[index].first;
        int val = mp[index].second;
        if (tcnt == cnt) return val;
        return tot;
    }
    void setAll(int val) {
        cnt++;
        tot = val;
    }
};