E - Notebook(tree&map)

E - Notebook(tree&map)

每个key 存一个vector 显然会存在问题，时空效率都很低。

因此考虑用一个vector，然后同时记录每个node 的father。

同时用map映射每个版本对应的结点。

这样复杂度是线性的$O(q)$qwq。

不然每次copy到map里 复杂度是$O(nq)$

#include
#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<<' ';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18