题解 P3402 【【模板】可持久化并查集】多次修改视作同一版本

· · 题解

多次修改 同一版本

本题解适合你在看了其他题解却感觉有点混乱的时候\

若b是a.b中深度更大的点(a,b都是该集合的代表元素)\ 我们应该使\

当且仅当$deep_{a}==deep_{b}$时，需要令\ $deep_{b}++$\ 你也许发现一个问题\ 每次合并时，不仅需要修改$a$的$father$,可能还需要更新新的父亲节点的$deep$\ 而其他题解里面很多是直接修改原来的版本的$b$的$deep

即我们每次合并可能需要多修改一次，来保证深度的正确递增\ 若是直接调用两次修改函数，一般的写法就会产生两个版本，\ 会多消耗很多空间。

于是我们想到，应该把两次修改当做

同一个版本

简而言之，就是判断当前点是新建一个副本，还是直接修改\ 当我们访问到一个点（修改时）：

  1. 当前版本新建的点 不需复制
  2. 旧版 需要复制

于是想到保存一个标记（时间点），通过比较，确定某点是什么时候建立的。\ 在修改函数开头加入如下语句：

void Modify(int &p, int L, int R, int x, int f,int d) {
    if (p <= last) {
        tree[++cnt] = tree[p];
        p = cnt;
    }
    //...其他一般操作
}

在主函数中，该版本的第一次修改前，加入如下语句：

last = cnt;

拓展的话，如果我们把每次的last都保存起来，还可以快速地确定某点是哪一次建立的，也许会有用处。