操作树

· · 题解

想要访问历史信息，要么用可持久化，要么用操作树。

可持久化是在线，操作树是离线。

看起来可持久化更好一点。

你说的对，但是操作树很好写，就这一点就够了。

访问历史信息并不能把所有的版本都记上去，所以考虑维护变化量。

直接开一个全局数据结构维护当前信息（类似扫描线和回滚莫队）。

而访问以前的版本信息实际上就是在一个操作链上做回滚操作，滚到链上某个点。

每次回滚实际上可以看成从第 u 个点跳到了链上的 v 点。

但回滚回去之后如果继续按这条链改下去就会覆盖掉以前的版本信息，所以考虑新开一条链。

而这就是一棵树，我们称它为操作树。

值得注意的一点是影响到结点 u 版本信息的地方只有 u 的祖先链。

因此只要没有对版本信息造成影响就不应该在操作树上新建端点。

对于本题，a 和 b 操作没有什么难度。

c 操作让你找公共部分，实际上就是两点的 \text{LCA} 的祖先链，个数即深度。

只需要离线之后在操作树上跑 \text{LCA} 即可。

直接上代码：

#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
using namespace std;

inline void cmax(int& x, int c) {
    x = max(x, c);
}
inline void cmin(int& x, int c) {
    x = min(x, c);
}

int _test_ = 1;

const int N = 3e5 + 5;

int n, fa[N], fav[N], ver[N], tot, f[N][20], dep[N], ans[N];
vector<int> g[N];
// ver 代表第 i 个操作之后的版本（结点）编号、
// fav 代表连向父亲的边上的权值

struct Q {
    int l, r, id;
};

void dfs(int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (auto x : g[u]) {
        if (x == fa)
            continue;
        dfs(x, u);
    }
}

int lca(int u, int v) {  // lca
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    int max_dep = 0;
    while ((1 << (max_dep + 1)) < dep[u])
        max_dep++;
    for (int i = max_dep; i >= 0; i--) {
        if (dep[u] - (1 << i) >= dep[v]) {
            u = f[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = max_dep; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

void init() {}

void clear() {}

void solve() {
    cin >> n;
    ver[0] = tot = 1;
    vector<Q> q;   // 离线
    int qtot = 0;  // 查询的个数
    for (int i = 1; i <= n; i++) {
        char c;
        int v;
        cin >> c >> v;
        if (c == 'a') {                   // a
            ver[i] = ++tot;               // 对应新的结点
            g[ver[v]].push_back(ver[i]);  // 建边
            g[ver[i]].push_back(ver[v]);
            fa[ver[i]] = ver[v];  // 记父亲
            fav[ver[i]] = i;
        }
        if (c == 'b') {
            qtot++;  // 需要回答，计数器加一
            ver[i] =
                fa[ver[v]];  // 找到版本，并删除（删除即撤销添加，即版本的父亲）
            ans[qtot] = fav[ver[v]];  // 记录答案
        }
        if (c == 'c') {
            qtot++;  // 需要回答
            int w;
            cin >> w;
            ver[i] = ver[v];  // 找到版本
            q.push_back(
                {ver[v], ver[w], qtot});  // 放到后面整棵树建好了用 lca 做（lca
                                          // 懒得写在线就干脆顺便把查询也离线）
        }
    }
    dfs(1, 0);
    int t = log2(n);
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }
    for (auto [x, y, id] : q) {
        ans[id] = dep[lca(x, y)] - 1;  // 减一是因为答案为路径上的边数而非点数
    }
    for (int i = 1; i <= qtot; i++)
        cout << ans[i] << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //  cin >> _test_;
    init();
    while (_test_--) {
        clear();
        solve();
    }
    return 0;
}

你会发现操作树并没有什么难度技巧。