可持久化栈

看到网上基本没有说得很详细的，所以我来讲一讲。

一种好的方法是直接用可持久化数组（线段树）来模拟栈，单次插入/删除时间复杂度 \(O(\log n)\)，空间复杂度 \(O(n \log n)\)。

这种方法也具有一定的优势——可以随机访问栈中元素，不过一般情况我们不需要可持久化栈支持这个操作。如果是这样的话，可持久化栈的单次插入的时间复杂度可以优化为 \(O(1)\)，空间复杂度也可以变为 \(O(n)\)。

例题：ABC273E - Notebook

插入操作

其实可持久化栈的本质就是用链表模拟栈，一个节点代表一个版本的栈顶，这些节点串联起来就得到了整个栈。

tot++;
val[tot] = x;
fa[tot] = cur;
cur = tot;

上面是向栈中插入新的元素 \(x\)，并同时生成新版本的方式。

tot：代表总结点数。

val[i]：节点 \(i\) 的值。

fa[i]：节点 \(i\) 的前驱。

cur：当前操作栈的栈顶。

删除操作

如果要更好的解释可持久化栈，你可以把它理解为每一个栈依赖于另一个版本的栈（就是 fa[i]），那个栈有依赖于一个版本的栈，最后直到空栈。这种依赖关系形成了一棵树。

cur = fa[cur];

这步更加简单，往回跳一个版本即可。

版本跳跃

如果希望栈立刻回到之前的某一个版本的栈顶：

cur = pos[x];

pos[i]：第 \(i\) 次操作后 cur 所在的栈顶。

pos[i] = cur; // 每次 插入/删除 操作结束后

ABC273E 模板题代码：

#include <bits/stdc++.h>
using namespace std;
int q, x, y, z, tot, cur, val[500005], fa[500005];
unordered_map<int, int> page;
char opt[7];

int main()
{
    scanf("%d", &q);
    while (q--)
    {
        scanf("%s", opt);
        if (opt[0] == 'A')
        {
            scanf("%d", &x);
            tot++;
            val[tot] = x;
            fa[tot] = cur;
            cur = tot;
        }
        else if (opt[0] == 'D')
            cur = fa[cur];
        else if (opt[0] == 'S')
        {
            scanf("%d", &y);
            page[y] = cur;
        }
        else
        {
            scanf("%d", &z);
            cur = page[z];
        }
        printf("%d ", cur ? val[cur] : -1);
    }
    return 0;
}