UOJ#195. 【ZJOI2016】大♂森林 LCT

題解

　　首先詢問都可以放到最後處理。

　　對于操作，我們把它差分一下離線下來。

　　現在的問題就是從第一棵樹到第 n 棵樹掃一遍，并不斷維護樹的形态。

　　容易感受到這棵樹會有删節點之類的操作，是以自然想到 LCT 。

　　但是要涉及一個節點的一些子節點換父親的時候LCT就GG了。

　　解決這個問題的辦法是建立虛點。虛點權值為 0 ，實點權值為 1，于是我們要維護鍊上點權和。

　　建虛點的規則是：

　　對于每一個操作 1 都建立一個虛點。即：将區間 [L,R] 的生長節點換成 x 的時候，建一個虛點，這個虛點的父親 在 [L,R] 中是 x ，否則是上一個生長節點對應的虛點。

　　對于每一個操作 2 ，直接把他連到上一個生長節點所對應的虛點上去就好了。

　　我們發現我們維護的LCT要擷取父親資訊，是以不友善換根。那就不換了！

　　那麼怎麼求兩點距離呢？

　　dis(x,y) = depth[x]+depth[y] - 2*depth[LCA(x,y)] 

　　LCT怎麼求LCA 呢？見代碼中的函數 Ask()

　　時間複雜度 $O(n\log n)$ 。

代碼

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
using namespace std;
typedef long long LL;
LL read(){
  LL x=0,f=0;
  char ch=getchar();
  while (!isdigit(ch))
    f|=ch=='-',ch=getchar();
  while (isdigit(ch))
    x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  return f?-x:x;
}
const int N=200005*2;
int n,m,oc=0;
struct Opt{
  int t,lev,x,y;
  Opt(){}
  Opt(int _t,int _lev,int _x,int _y){
    t=_t,lev=_lev,x=_x,y=_y;
  }
}o[N*3];
bool cmpo(Opt a,Opt b){
  return a.t!=b.t?a.t<b.t:a.lev<b.lev;
}
int lv[N],rv[N],id[N],ans[N];
namespace lct{
  int size[N],val[N],fa[N],son[N][2];
  int n;
  void pushup(int x){
    size[x]=size[son[x][0]]+val[x]+size[son[x][1]];
  }
  int Add(int v){
    val[++n]=v,pushup(n);
    return n;
  }
  void init(){
    n=0;
    id[1]=Add(1);
  }
  int isroot(int x){
    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
  }
  int wson(int x){
    return son[fa[x]][1]==x;
  }
  void rotate(int x){
    if (isroot(x))
      return;
    int y=fa[x],z=fa[y],L=wson(x),R=L^1;
    if (!isroot(y))
      son[z][wson(y)]=x;
    fa[x]=z,fa[y]=x,fa[son[x][R]]=y;
    son[y][L]=son[x][R],son[x][R]=y;
    pushup(y),pushup(x);
  }
  void splay(int x){
    for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])
      if (!isroot(y))
        rotate(wson(x)==wson(y)?y:x);
  }
  int access(int x){
    int t;
    for (t=0;x;t=x,x=fa[x])
      splay(x),son[x][1]=t,pushup(x);
    return t;
  }
  void refather(int x,int y){
    access(x),splay(x),son[x][0]=fa[son[x][0]]=0,pushup(x);
    fa[x]=y;
  }
  int Ask(int x,int y){
    int ans=0;
    access(x),splay(x),ans=size[x];
    int z=access(y);
    splay(y),ans+=size[y];
    access(z),splay(z),ans-=size[z]*2;
    return ans;
  }
}
int main(){
  n=read(),m=read();
  lct::init();
  lv[1]=1,rv[1]=n;
  lct::refather(lct::Add(0),1);
  int pre=2,cnt=1,q=0;
  for (int i=1;i<=m;i++){
    int type=read();
    if (type==0){
      int L=read(),R=read();
      cnt++,lv[cnt]=L,rv[cnt]=R;
      o[++oc]=Opt(1,i,id[cnt]=lct::Add(1),pre);
    }
    else if (type==1){
      int L=read(),R=read(),x=read();
      L=max(L,lv[x]),R=min(R,rv[x]);
      if (L<=R){
        int now=lct::Add(0);
        if (L>1)
          lct::refather(now,pre);
        o[++oc]=Opt(L,i,now,id[x]);
        o[++oc]=Opt(R+1,i,now,pre);
        pre=now;
      }
    }
    else {
      int k=read(),x=read(),y=read();
      o[++oc]=Opt(k,(++q)+m,id[x],id[y]);
    }
  }
  sort(o+1,o+oc+1,cmpo);
  for (int i=1,j=1;i<=n;i++){
    while (j<=oc&&o[j].t<=i){
      int k=o[j].lev,x=o[j].x,y=o[j].y;
      if (k<=m)
        lct::refather(x,y);
      else
        ans[k-m]=lct::Ask(x,y);
      j++;
    }
  }
  for (int i=1;i<=q;i++)
    printf("%d\n",ans[i]);
  return 0;
}