Notebook
题意
有 \(q\) 次操作。
现在你有一个空序列 \(a\) 和一本 \(10^9\) 页的笔记本，每页纸上都有一个空序列。
每次操作是以下四种中的一种：
ADD x，表示在 \(a\) 的末尾插入一个整数 \(x\)。DELETE，表示删除 \(a\) 的末尾的一个数，如果 \(a\) 序列为空则什么也不干。SAVE y，表示将第 \(y\) 页纸上的序列替换为 \(a\)。LOAD z，表示将 \(a\) 换成第 \(z\) 页纸上的序列。
对于每次操作，你需要输出操作完后的 \(a\) 序列的最后一个数，如果 \(a\) 为空则输出 -1，输出用空格分隔。
数据范围
- \(1 \leqslant q \leqslant 5 \times 10^5\)。
- \(1 \leqslant x,y,z \leqslant 10^9\)。
思路
如果只有 ADD 和 DELETE，应该都会做，栈模拟。
经过观察，我们可以发现：SAVE 和 LOAD 两种操作既耗时间又耗空间，但两种操作都与原序列有些关联！
ADD 就相当于往下 dfs，DELETE 就相当于回溯，欸，这不就是 dfs 树吗？考虑把序列建成一个树。
假设现在考虑的节点编号为 \(now\)，节点数量为 \(n\)。
\(now\) 初始可以设为 \(0\)。
ADD x，就是给 \(now\) 建立一个儿子节点 \(n + 1\)，节点记录的数为 \(x\)，并将 \(now\) 设为 \(n + 1\)。DELETE，就是将 \(now\) 改为 \(now\) 的父亲节点编号。SAVE y，给第 \(y\) 页纸记录一个存档的节点编号，这个编号也就是 \(now\)。LOAD z，将 \(now\) 设为第 \(z\) 张纸记录的存档节点编号。
由于页数有 \(10^9\)，所以要用 map 存储每页纸存储的存档节点编号。
复杂度
- 时间：\(O(q \log q)\)。
- 空间：\(O(q)\)。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int Q = 5e5 + 10;
struct ID {
int x, fa; // x 记录数值，fa 记录父亲节点编号
} a[Q];
int q, x, n, now;
string s;
map<int, int> mp; // 每页纸上记录的存档的节点编号
int main () {
ios::sync_with_stdio(0), cin.tie(0);
a[0].x = -1;
for (cin >> q; q; q--) {
cin >> s;
if (s[0] != 'D') {
cin >> x;
}
if (s == "DELETE") { // 回溯
now = a[now].fa;
} else if (s == "ADD") { // 新建节点
a[++n] = {x, now}, now = n;
} else if (s == "SAVE") { // 存档
mp[x] = now;
} else { // 取档
now = mp[x];
}
cout << a[now].x << ' ';
}
return 0;
}