E - Notebook(tree&map)

E - Notebook(tree&map)

每個key 存一個vector 顯然會存在問題，時空效率都很低。

是以考慮用一個vector，然後同時記錄每個node 的father。

同時用map映射每個版本對應的結點。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,n,m,x;string s;
struct o{ll x,fa;}a[500005];
map<ll,ll>b;
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>N;a[0].x=-1;
  while(N--){
    cin>>s;
    if(s=="ADD")cin>>x,a[++n]=(o){x,m},m=n;
    if(s=="DELETE")m=a[m].fa;
    if(s=="SAVE")cin>>x,b[x]=m;
    if(s=="LOAD")cin>>x,m=b[x];
    cout<<a[m].x<<' ';
  }
}