赛时没做出来，晚上补了一下，发现是一种很好玩的 数据结构。
由于可以离线又要支持删除后 $k$ 个又要支持撤销操作，不会写主席树只能选择操作树。
对序列按照时间建成一颗操作树，处于某个点的回合时，这个序列的样子就是它以及它的祖先。
来依次考虑某个操作，设当前是序列的末尾是 $p$ 号元素。
加操作，直接在 $p$ 下面挂一个儿子，然后 $p$ 变成它即可。
减操作，此时我们发现需要跳 $k$ 级祖先，就需要倍增了，这个操作于是解决。
撤销操作，其实可以实时记录加减操作的一个栈，这个时候把栈顶弹出，把 $p$ 变成现在的栈顶即可。
询问操作，留到最后建完表达式树再做。
我们发现询问就是问每个点向上构成的序列中的元素个数，可以用类似莫队的方法解决，但是这一部分是 $O(n)$ 的，于是就过了，代码：
#include <bits/stdc++.h> #define For(i, a, b) for (int i = (a); i <= (b); i ++) #define foR(i, a, b) for (int i = (a); i >= (b); i --) using namespace std; stack <int> st; int p, q, x, cnt, res; int f[1000005][20], val[1000005]; int b[1000005], ans[1000005], pos[1000005]; char op[1000005]; vector <int> G[1000005]; void add (int x) { b[x] ++; if (b[x] == 1) ++ res; } void rem (int x) { b[x] --; if (b[x] == 0) -- res; } void dfs (int u) { if (u) add (val[u]); ans[u] = res; for (int v : G[u]) dfs (v); if (u) rem (val[u]); } signed main () { st.push (0); scanf ("%d", &q); For (i, 1, q) { op[i] = getchar (); while (op[i] == ' ' || op[i] == '\n') op[i] = getchar (); if (op[i] == '+') { scanf ("%d", &x); f[++ cnt][0] = p; val[cnt] = x; For (j, 1, 20) f[cnt][j] = f[f[cnt][j - 1] ][j - 1]; p = cnt; } else if (op[i] == '-') { scanf ("%d", &x); foR (j, 20, 0) { if (x >= (1 << j) ) { x -= (1 << j); p = f[p][j]; } } } else if (op[i] == '!') { st.pop (); p = st.top (); } pos[i] = p; if (op[i] != '?' && op[i] != '!') st.push (p); } For (i, 1, cnt) G[f[i][0] ].push_back (i); dfs (0); For (i, 1, q) if (op[i] == '?') cout << ans[pos[i] ] << '\n'; return 0; }