题目概述

有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的距离。

解题报告

很明显只需要在最终树上询问就行了，然后区间修改太变态了，我们用离线+扫描线来维护每棵树的LCT。考虑怎么维护加点和改根这两个操作，加点可以直接找到父亲和儿子插进去，但是改根操作会引起大量信息改动导致爆炸，所以我就不会了……

LCT建辅助点太神仙了……对于每个改根操作，我们都建一个辅助点（辅助点没有点权），然后对于每个加点操作，我们都连向最近的改根操作，每个改根操作也连向上一个改根操作。一旦改根了，我们就把这个改根操作和上一个改根操作断开，连向改成的根节点，这样就完成了大量的信息改动。

但是这样连边有个小问题，就是询问 $x,y$ 的时候，$x,y$ 可能会经过辅助点而不是经过了实际的点，导致统计出错，所以我们需要把点权改成边权，只有加点（实点指向辅助点）的时候才有边权，否则没有边权，这样就没有问题了。

最后还有一个很恶心的事情，就是换根操作可能无效。不过由于加点是连续的，所以我们对于每个换根操作，将操作的区间和根节点存在的区间取并，就可以保证换根操作都是有效的。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const int maxn=100000,maxm=200000,maxt=maxm*3;

int n,m,ID[maxm+5];struct data {int tp,A,B,C;} q[maxm+5];
int son[maxt+5][2],fa[maxt+5],si[maxt+5];bool ex[maxt+5],flip[maxt+5];
int pre[maxm+5],ans[maxm+5];vector<int> A[maxn+5],B[maxn+5],C[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void getdata(data &a) {readi(a.tp);readi(a.A);readi(a.B);if (a.tp) readi(a.C);}
#define is_ro(p) (son[fa[p]][0]!=(p)&&son[fa[p]][1]!=(p))
#define Son(p) (son[fa[p]][1]==(p))
inline void Pushup(int p) {si[p]=si[son[p][0]]+ex[p]+si[son[p][1]];}
inline void Rotate(int t){
    int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
inline void Pushdown(int p) {if (flip[p]) flip[p]^=1,Addflip(son[p][0]),Addflip(son[p][1]);}
inline void Splay(int p){
    static int stk[maxn+5],top;stk[top=1]=p;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
inline void Link(int x,int y) {Makero(x);Makero(y);fa[y]=x;}
inline void Cut(int x,int y) {Makero(x);Access(y);Splay(x);son[x][1]=fa[y]=0;Pushup(x);}
inline int Ask(int x,int y) {Makero(x);Access(y);Splay(y);return si[y];}
inline void Update(int x,int f) {Splay(x);ex[x]=f;Pushup(x);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);m++;for (int i=2;i<=m;i++) getdata(q[i]);Link(1,(m<<1)+1);Link((m<<1)+1,m+1);
    for (int i=2,now=1,lst=1;i<=m;i++)
        if (q[i].tp==2) C[q[i].A].pb(i); else{
            if (!q[i].tp) ID[q[i].C=++now]=i,Update((m<<1)+now,1); else{
                int now=ID[q[i].C];if (now) q[i].A=max(q[i].A,q[now].A),q[i].B=min(q[i].B,q[now].B);
                if (q[i].A<=q[i].B) Link(m+lst,m+i);
            }pre[i]=lst;if (q[i].A<=q[i].B) A[q[i].A].pb(i),B[q[i].B+1].pb(i),q[i].tp?lst=i:0;
        }
    for (int i=1;i<=n;i++){
        for (int j=0,si=B[i].size(),u;j<si;j++)
            if (q[u=B[i][j]].tp) Cut(q[u].C,m+u),Link(m+pre[u],m+u);
            else Cut(q[u].C,(m<<1)+q[u].C),Cut((m<<1)+q[u].C,m+pre[u]);
        for (int j=0,si=A[i].size(),u;j<si;j++)
            if (q[u=A[i][j]].tp) Cut(m+pre[u],m+u),Link(q[u].C,m+u);
            else Link(q[u].C,(m<<1)+q[u].C),Link((m<<1)+q[u].C,m+pre[u]);
        for (int j=0,si=C[i].size(),u;j<si;j++) u=C[i][j],ans[u]=Ask(q[u].B,q[u].C);
    }for (int i=1;i<=m;i++) if (q[i].tp==2) printf("%d\n",ans[i]);return 0;
}