【ZJOI2016】大森林

mrsrz 9月 15, 2020

LCT

题目大意：

给定 $n$ 棵树，每棵树一开始只有一个编号为 $1$ 的结点。

每棵树有一个生长结点，初始均为 $1$。

要求支持以下操作：

给定 $l,r$，令编号 $l\sim r$ 的树都新建一个结点，结点编号为之前 $1$ 操作的个数 $+2$。新结点的父亲为该树对应的生长结点。
给定 $l,r,x$，令编号 $l\sim r$ 的树的生长结点变为编号 $x$ 的结点。如果这棵树没有编号为 $x$ 的结点则不变。
给定 $x,u,v$，询问第 $x$ 棵树上编号为 $u$ 和 $v$ 的结点的距离。

题解：

对操作离线，并对每棵树分别考虑。

可以发现，对于 $[l,r]$ 的操作，只会在 $l-1$ 变到 $l$ 和 $r$ 变到 $r+1$ 时产生影响。

那么我们将操作变成这几个时间点来执行，这样就只需要在一棵树上进行操作了。

当生长结点变化的时候，这个结点下面的很多点的父亲都会改变，不能直接处理。

可以使用建虚点的方式。我们对每个修改生长结点的操作，都新建一个虚点，然后接下来生长的结点都长到这个虚点上就可以了。撤销这个操作的时候，我们只需要将这个虚点连接到上一个虚点，那么就相当于这个修改生长结点的操作没有执行过了。

这些操作都可以用 LCT 轻松维护。对于边权的问题，转化为点权就好了。

由于树的根固定，父子关系不变，所以不能使用 makeroot 操作，我们在处理询问的时候只能使用 $\mathrm{dep}(u)+\mathrm{dep}(v)-2\cdot\mathrm{dep}(\mathrm{LCA}(u,v))$ 的方式。动态树上的 LCA 可以用两次 access 操作求得。

注意如果编号 $x$ 的结点不存在，则不修改生长结点，因此修改生长结点的操作区间需要和对应结点所在区间取交。

时间复杂度 $O(m\log m+n)$。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+5,M=1e5+5;
namespace lct{
    int ch[N][2],val[N],fa[N],sum[N];
    inline bool ckr(int x,int p=1){return ch[fa[x]][p]==x;}
    inline bool isroot(int x){return!(ckr(x)||ckr(x,0));}
    inline void update(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];}
    void rotate(int x){
        int y=fa[x],z=fa[y],k=ckr(x);
        if(!isroot(y))ch[z][ckr(y)]=x;
        fa[x]=z,fa[y]=x,fa[ch[x][!k]]=y;
        ch[y][k]=ch[x][!k],ch[x][!k]=y;
        update(y);
    }
    void splay(int x){
        for(;!isroot(x);rotate(x))
        if(!isroot(fa[x]))rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
        update(x);
    }
    inline int access(int x){
        int t=0;for(;x;ch[x][1]=t,t=x,x=fa[x])splay(x);return t;
    }
    inline void link(int x,int y){access(y),splay(y),fa[y]=x;}
    inline void cut(int x,int y){access(y),splay(y);fa[ch[y][0]]=0,ch[y][0]=0;update(y);}
}
int n,m,id=1,ans[N],fa[N],L[N],R[N];
vector<pair<int,int> >A1[M],D1[M],A0[M],D0[M];
vector<pair<pair<int,int>,int> >Q[M];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    L[1]=1,R[1]=n;
    lct::link(1,2*m+1);
    fa[2*m+1]=1;
    for(int i=2*m+2;i<=3*m;++i)lct::link(i-1,i),fa[i]=i-1;
    for(int i=1;i<=m;++i){
        ans[i]=-1;
        int op;
        cin>>op;
        switch(op){
            case 0:{
                int l,r;
                cin>>l>>r;
                ++id;
                L[id]=l,R[id]=r;
                A0[l].emplace_back(i,id),D0[r+1].emplace_back(i,id);
                break;
            }
            case 1:{
                int l,r,x;
                cin>>l>>r>>x;
                l=max(L[x],l),r=min(R[x],r);
                if(l<=r)A1[l].emplace_back(i,x),D1[r+1].emplace_back(i,x);
                break;
            }
            case 2:{
                int x,u,v;
                cin>>x>>u>>v;
                Q[x].emplace_back(make_pair(u,v),i);
                break;
            }
        }
    }
    for(int T=1;T<=n;++T){
        for(auto it:A0[T]){
            int tim=it.first,x=it.second;
            lct::val[x+m]=1;
            lct::link(x+m,x),lct::link(tim+2*m,x+m);
            fa[x]=x+m,fa[x+m]=tim+2*m;
        }
        for(auto it:D0[T]){
            int tim=it.first,x=it.second;
            lct::cut(x+m,x),lct::cut(fa[x+m],x+m);
            fa[x]=fa[x+m]=0;
        }
        for(auto it:A1[T]){
            int tim=it.first,x=it.second;
            lct::cut(fa[tim+2*m],tim+2*m);
            lct::link(x,tim+2*m);
            fa[tim+2*m]=x;
        }
        for(auto it:D1[T]){
            int tim=it.first,x=it.second;
            lct::cut(fa[tim+2*m],tim+2*m);
            lct::link((tim==1)?1:tim-1+2*m,tim+2*m);
            fa[tim+2*m]=(tim==1)?1:tim-1+2*m;
        }
        for(auto it:Q[T]){
            int u=it.first.first,v=it.first.second;
            lct::access(u);
            lct::splay(u);int X=lct::sum[u];
            int LCA=lct::access(v);lct::splay(v);int Y=lct::sum[v];
            lct::access(LCA),lct::splay(LCA);
            int Z=lct::sum[LCA];
            ans[it.second]=X+Y-2*Z;
        }
    }
    for(int i=1;i<=m;++i)if(ans[i]!=-1)cout<<ans[i]<<'\n';
    return 0;
}