永続データ構造．
Vector \(a\) 自身でなく，\(a\) の編集履歴を保存しておき， 履歴におけるタイミングに跳ぶことで復元する．
今回は tree \(T\) を永続データ構造としてもつ．
出力クエリ
必要な情報は，\(a\) の末端．これは \(T\) における頂点 \(v\)． \(v\) の時点において，\(a\) は末端が \(v\) となる． より正確には，root から \(v\) への path が \(a\) となる．
追加クエリ
\(T\) に vertex を追加して，そこに遷移する．
削除クエリ
今いる \(T\) における頂点から，一つ前に戻る． \(T\) の parent にあたる．
実装
Root は \(a\) が empty であることを示す． Empty のときにも delete ができるように， root の from を root 自身にしておく．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll q; cin >> q;
vector<EDGE> tr; // tree
map<ll,ll> mp; // page -> (vertex on tree)
tr.emplace_back( 0, -1 ); // root of tree // the from of root is itself
ll v = 0; // vertex on tree
rep(qi,q){
string t; cin >> t;
if(t == "DELETE"){
v = tr[v].from;
}else{
ll x; cin >> x;
if(t == "ADD"){
tr.emplace_back( v, x );
v = tr.size() - 1;
} else if(t == "SAVE"){
mp[x] = v;
}else{
v = mp[x];
}
}
printf("%d\n", tr[v].val);
}
return 0;
}
