题解 P3348 【[ZJOI2016]大森林】

· · 题解

由于最近在补文化课，现在做题的速度贼慢……

昨天和今天一直在理解虚点的做法，理解了很久，不过我对 LCT 的认识也更加深入了。

前置知识：深入理解 LCT，不能记板子！

让我们看看这道题的操作：

操作 0： 区间加结点

操作 1： 区间换根（生长结点）

操作 2： 单点查询树上距离

一看不可做，大力 O(n^2\log n) 肯定是不行的……

那么让我们挖掘一下操作的性质。

1、后续的操作 0,1 不会影响前面操作 2 的结果

因为没有删点也没有区间断边，所以这满足离线的基本条件。

离线后我们将 n 棵树缩成一棵树，然后就操作 0 就没了。

突然一看操作 2 询问的是边数？那我们就多加一个结点为边权，权值为 1，否则权值为 0，询问的答案为 sum_x+sum_y-2\times sum_{lca(x,y)}

2、对于操作 0,1 建虚点

操作 0 建边权的点，操作 1 建无边权的点。每次操作 0 和操作 1 都连向上一个操作 1，这样保证默认生长结点为 1。若满足前提条件（有坑），那么这个操作 1 在 0 位置连向 id_x（id_x 为第 x 个生长结点在 LCT 中的位置），在 r+1 位置再断掉。询问便是最后询问啦。

相当于我们离线之后先按操作位置排序，再按是否为询问操作排序，最后按操作顺序排序。在最开始的时候要另外申请两个结点，表示第一个结点和第 0 次操作 1

我深知没图的痛苦，所以我们来解释一下样例吧。

五个操作排序后这样子的：

0 1 5
0 1 4
2 1 1 3
1 2 4 2
2 2 1 3

最初树的形态：

询问结束后树的形态：

首先两个 0 操作：

第一次询问操作是从图中的 1 到 5，答案为 1。

然后 1 操作 cut 后 link：

第二次询问前树的形态：

第二次询问是从图中的 1 到 5，答案为 2

接下来就是 LCT 的基本操作 + 在 LCT 上找 lca 了，时间复杂度 O(n\log n)。虽然看上来数据很小，但是 LCT 自带大常数 + 一次找 lca 需要 6 倍常数，所以跑得超级慢。。。

Update:2019.03.29 因为在两个实点的路径上有可能存在虚点，所以需要差分答案。 $Code\ Below: 
#include <bits/stdc++.h>
using namespace std;
const int maxn=400000+10;
int n,m,last,cnt,ch[maxn][2],fa[maxn],val[maxn],sum[maxn];
int L[maxn],R[maxn],id[maxn],ans[maxn],ind,qn,tot;

struct Query{
    int pos,id,x,y;
    Query(int pos=0,int id=0,int x=0,int y=0):pos(pos),id(id),x(x),y(y){}
}q[maxn];

inline bool cmp(const Query &a,const Query &b){
    return (a.pos!=b.pos)?a.pos<b.pos:a.id<b.id;
}

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

inline void pushup(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];}
inline bool nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline void rotate(int x){
    int y=fa[x],z=fa[y],k=(ch[y][1]==x),u=ch[x][k^1];
    if(nrt(y)) ch[z][ch[z][1]==y]=x;
    ch[y][k]=u;ch[x][k^1]=y;
    if(u) fa[u]=y;fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}
inline void splay(int x){
    int y,z;
    while(nrt(x)){
        y=fa[x],z=fa[y];
        if(nrt(y)) rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
        rotate(x);
    }
}
inline int access(int x){
    int y=0;
    for(;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y,pushup(x);
    return y;
}
inline void link(int x,int y){splay(x);fa[x]=y;}
inline void cut(int x){access(x),splay(x);fa[ch[x][0]]=0;ch[x][0]=0;pushup(x);}
inline void newnode(int x){cnt++;val[cnt]=sum[cnt]=x;}
inline int query(int x,int y){
    int ans=0,lca;
    access(x),splay(x),ans+=sum[x];
    lca=access(y),splay(y),ans+=sum[y];
    access(lca),splay(lca),ans-=2*sum[lca];
    return ans;
}

int main()
{
    n=read(),m=read();
    newnode(1);L[1]=1;R[1]=n;id[ind=1]=1;
    newnode(0);link(2,1);last=2;
    int op,l,r,x,u,v;
    for(int i=1;i<=m;i++){
        op=read();
        if(op==0){
            l=read(),r=read();
            newnode(1);L[++ind]=l;R[ind]=r;id[ind]=cnt;
            q[++tot]=Query(1,i-m,cnt,last);
        }
        if(op==1){
            l=read(),r=read(),x=read();
            l=max(l,L[x]);r=min(r,R[x]);
            if(l<=r){
                newnode(0);link(cnt,last);
                q[++tot]=Query(l,i-m,cnt,id[x]);
                q[++tot]=Query(r+1,i-m,cnt,last);
                last=cnt;
            }
        }
        if(op==2){
            x=read(),u=read(),v=read();
            q[++tot]=Query(x,++qn,id[u],id[v]);
        }
    }
    sort(q+1,q+tot+1,cmp);
    for(int i=1,j=1;i<=n;i++)
        for(;i==q[j].pos;j++){
            if(q[j].id<=0) cut(q[j].x),link(q[j].x,q[j].y);
            else ans[q[j].id]=query(q[j].x,q[j].y);
        }
    for(int i=1;i<=qn;i++) printf("%d\n",ans[i]);
    return 0;
}