题解 P3348 【[ZJOI2016]大森林】
Owen_codeisking
2019-03-08 17:37:38
由于最近在补文化课，现在做题的速度贼慢……
昨天和今天一直在理解虚点的做法，理解了很久，不过我对 $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$
我深知没图的痛苦，所以我们来解释一下样例吧。
五个操作排序后这样子的：
```cpp
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$
$ljc1301$ 在省选的时候问我为什么没有人直接暴力 $split(x,y)$ 求出 $sum$，我当时没想到，现在特地解释一下。
因为在两个实点的路径上有可能存在虚点，所以需要差分答案。
$Code\ Below:$
```cpp
#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;
}
```