CF1858E1 做题笔记

题目链接

赛时没做出来，晚上补了一下，发现是一种很好玩的 数据结构。

由于可以离线又要支持删除后 $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;
}