不得不说，ZJOI 的可做题都是数据结构题

 这个东西显然不能在线，所以考虑离线以后从左往右扫过去。同时询问可以把整棵树处理好再处理。

那么我们要处理的就是修改生长结点引发的孩子关系变化。

考虑对每个修改开一个虚点，然后每次生长出的点挂在最近的修改下，相邻修改前后相连，不难发现这种连法像多叉转二叉一样，不会改变实点距离。那么转换就是把对应虚点从它父亲上切下来，连到对应结点上。

这个 LCT 显然不能换根，因此要求 LCA，方法是先 access(u)，然后 access(v)，那么 v 跳到根碰到的最后一个点就是 LCA。

对于一些树上没有相应结点，判一下就可以了。

#include<cstdio>
#include<vector>
#include<utility>
#define For(i,A,B) for(i=(A);i<=(B);++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=100050;
const int BUF=1<<22;
char rB[BUF],*rS,*rT,wB[BUF+50],*wT=wB;
inline char gc(){return rS==rT&&(rT=(rS=rB)+fread(rB,1,BUF,stdin),rS==rT)?EOF:*rS++;}
inline void flush(){fwrite(wB,1,wT-wB,stdout);wT=wB;}
inline int rd(){
    char c=gc();
    while(c<48||c>57)c=gc();
    int x=c&15;
    for(c=gc();c>=48&&c<=57;c=gc())x=x*10+(c&15);
    return x;
}
short buf[15];
inline void wt(int x){
    short l=-1;
    if(wT-wB>BUF)flush();
    while(x>9){
        buf[++l]=x%10;
        x/=10;
    }
    *wT++=x|48;
    while(l>=0)*wT++=buf[l--]|48;
    *wT++='\n';
}
int lb[N*2],rb[N*2],bl[N*2],f[N*2],ch[N*2][2],sum[N*2],ans[N*2];
bool val[N*2];
vector<pair<int,int> > L[N],Q[N];
vector<int> R[N],id[N];
inline void chkmin(int &a,int b){if(b<a)a=b;}
inline void chkmax(int &a,int b){if(a<b)a=b;}
inline bool nrt(int o){return ch[f[o]][0]==o||ch[f[o]][1]==o;}
inline bool dir(int o){return ch[f[o]][1]==o;}
inline void pushup(int o){sum[o]=val[o]+sum[ch[o][0]]+sum[ch[o][1]];}
inline void rot(int o){
    int fa=f[o];
    bool d=dir(o);
    f[o]=f[fa];
    if(nrt(fa))ch[f[o]=f[fa]][dir(fa)]=o;
    if(ch[fa][d]=ch[o][d^1])f[ch[fa][d]]=fa;
    f[ch[o][d^1]=fa]=o;
    pushup(fa);
}
inline void splay(int o){
    for(;nrt(o);rot(o))if(nrt(f[o]))rot((dir(o)^(dir(f[o])))?o:f[o]);
    pushup(o);
}
inline int access(int x){
    int y=0;
    for(;x;x=f[y=x]){
        splay(x);
        ch[x][1]=y;
        pushup(x);
    }
    return y;
}
inline void link(int x,int y){
    access(x);splay(x);
    f[x]=y;
}
inline void cut(int x){
    access(x);splay(x);
    f[ch[x][0]]=0;ch[x][0]=0;
//其实这个 cut 是错的，但因为 cut 完立即 link 时进行了 pushup，所以这里可以不用 pushup
}
inline int lca(int x,int y){
    int z,s;
    access(x);splay(x);s=sum[x];
    z=access(y);splay(y);s+=sum[y];
    access(z);splay(z);
    return s-sum[z]*2;
}
int main(){
    int n=rb[1]=rd(),m=rd(),i,j,opt,x,y,z,tot=1,cl=0,ql=0;
    bl[1]=lb[1]=1;
    For(i,1,m){
        opt=rd();x=rd();y=rd();
        if(!opt){
            bl[++tot]=cl;
            lb[tot]=x;rb[tot]=y;
        }else if(opt==1){
            chkmax(x,lb[z=rd()]);chkmin(y,rb[z]);
            if(x>y)continue;
            L[x].pb(mp(++cl,z));
            if(y<n)R[y+1].pb(cl);
        }else{Q[x].pb(mp(y,rd()));id[x].pb(++ql);}
    }
    For(i,1,tot){
        val[i]=1;
        if(i>1)link(i,!bl[i]?1:bl[i]+tot);
    }
    For(i,1,cl)link(i+tot,i>1?i-1+tot:1);
    For(i,1,n){
        For(j,0,(int)R[i].size()-1){
            cut(R[i][j]+tot);
            link(R[i][j]+tot,R[i][j]>1?R[i][j]-1+tot:1);
        }
        For(j,0,(int)L[i].size()-1){
            cut(L[i][j].fi+tot);
            link(L[i][j].fi+tot,L[i][j].se);
        }
        For(j,0,(int)Q[i].size()-1)ans[id[i][j]]=lca(Q[i][j].fi,Q[i][j].se);
    }
    For(i,1,ql)wt(ans[i]);
    flush();
    return 0;
}

View Code