对于每个\(1\)操作建一个虚点，以后的\(0\)操作都连在最近建好的虚点上。这样每次整体嫁接的时候，直接把这个虚点断掉它原来的父亲，再\(link\)过去就可以了
求在\(x\)位置的两点之间距离 , 只要之前的换点加点操作完成 , 就可以计算 , 而且也要马上计算 , 之后树的形态就又要变了 , 这样保证了复杂度
关于代码 : 先按思路把离线的事件处理出来
然后发现这种离线的利用虚点的转移只能用\(LCT\)维护
注意 : 只有实点才算\(size\) , 并统计到路径长度中去 , 利用的虚点不算\(size\)
还有\(LCT\)上不\(makeroot\)时求\(LCA\)的求法
注释重构于19.3.29
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}
const int MAXN=3e5+5;
const int MAXM=2e5+5;
struct Query{
int pos,id,x,y;
inline friend bool operator<(Query a,Query b){
if(a.pos==b.pos) return a.id<b.id;
return a.pos<b.pos;
}
}q[MAXM];
int Qcnt,Acnt;
int at[MAXN],L[MAXN],R[MAXN],ans[MAXN];
int n,m,p,aux,real;
namespace LCT{
int ch[MAXN][2],fa[MAXN],size[MAXN],val[MAXN];
int st[MAXN],top;
#define ls (ch[rt][0])
#define rs (ch[rt][1])
inline bool chk(int x){return ch[fa[x]][1]==x;}
inline bool isnotroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline void pushup(int rt){size[rt]=size[ls]+size[rs]+val[rt];}//只要算实点
inline void rotate(int x){
int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
ch[y][k]=w,fa[w]=y;
if(isnotroot(y)) ch[z][chk(y)]=x; fa[x]=z;
ch[x][k^1]=y,fa[y]=x;
pushup(y);pushup(x);
}
inline void splay(int x){
while(isnotroot(x)){
int y=fa[x];
if(isnotroot(y)){
if(chk(x)==chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
inline int access(int x){
int y=0;
for(;x;x=fa[y=x])
splay(x),ch[x][1]=y,pushup(x);
return y;//access(y)时最后跳的虚边的父亲就是lca,即最后的y
}
inline void link(int x,int y){
splay(x);//不能makeroot,只能splay
fa[x]=y;//只有根节点才能连边
}
inline void cut(int x){//和它上面的点断开
access(x);splay(x);
ch[x][0]=fa[ch[x][0]]=0;
pushup(x);
}
#undef ls
#undef rs
}using namespace LCT;
int main(){
n=read(),m=read();
real=1,size[1]=1,val[1]=1,at[1]=1,L[1]=1,R[1]=n;//初始时只有1一个实点
link(p=aux=2,1);
for(int i=1;i<=m;i++){
int op=read(),x=read(),y=read();
if(op==0){
link(at[++real]=++p,aux);///新建一个点连到虚点上去,并记录第real个实点在哪(是所有编号中的第几个)
size[p]=1,val[p]=1;//更新val[]!!! (注意只有这样的实点才有权值)
L[real]=x,R[real]=y;
}
if(op==1){
int t=read();
x=max(x,L[t]),y=min(y,R[t]);//有些树还没这个点
if(x>y) continue;
link(++p,aux);///新建一个点连到虚点上去
//size[p]=0,val[p]=0; 虚点没有val[],不算进路径上有size[]个点
//先按思路把离线的事件处理出来
q[++Qcnt]=(Query){x,i-m,p,at[t]};///到了x就把虚点换成这个 -m是为了使换点操作在加点操作前面.
q[++Qcnt]=(Query){y+1,i-m,p,aux};//到了y+1就换回去
aux=p;//更换虚点了!!! 之后的点要放到新点的下面
}
if(op==2) q[++Qcnt]=(Query){x,++Acnt,at[y],at[read()]};//在x位置的两点之间距离,只要之前的换点加点操作完成,就可以计算,而且也要马上计算,之后树的形态就又要变了
}
sort(q+1,q+Qcnt+1);
for(int i=1;i<=Qcnt;i++){
if(q[i].id>0){
int x=q[i].x,y=q[i].y,&sum=ans[q[i].id];
//由于根节点始终为1,不能makeroot后求路径,所以要用到lca.本题中步数=size[x]+size[y]-2*size[lca].
access(x);splay(x);sum+=size[x];
int lca=access(y);splay(y);sum+=size[y];
access(lca);splay(lca);sum-=size[lca]*2;//打起来真的舒服
}
else{ // 这种离线的利用虚点的转移只能用LCT维护
cut(q[i].x);//和它上面的点断开
link(q[i].x,q[i].y);//然后连到新的点上去
}
}
for(int i=1;i<=Acnt;i++)
printf("%d\n",ans[i]);
}