content/datastructures/persistent.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template<typename T>
struct persistent {
	int& time;
	vector<pair<int, T>> data;

	persistent(int& time, T value = {}) 
		: time(time), data(1, {2*time, value}) {}
	
	T get(int t) {
		return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second;
	}
	
	int set(T value) {
		time++;
		data.push_back({2*time, value});
		return time;
	}
};