Cptraser/ 三月 21, 2019/ 2019.3/ 0 comments

【模板】Link Cut Tree (动态树)

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=3e5+5,Size=1<<19;

int Fa[Maxn],tr[Maxn][2],v[Maxn],s[Maxn],st[Maxn];
bool r[Maxn];

bool nroot(int x){return tr[Fa[x]][0]==x||tr[Fa[x]][1]==x;}
void PushUp(int x){s[x]=s[tr[x][0]]^s[tr[x][1]]^v[x];}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushDown(int x){
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[Fa[x]][1];}
void Rotate(int x){
    int y=Fa[x],z=Fa[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;//details
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)Fa[w]=y;Fa[y]=x,Fa[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))st[++top]=y=Fa[y];
    while(top)PushDown(st[top--]);//details
    for(int S;S=Fa[x],nroot(x);Rotate(x))if(nroot(S))//details
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=Fa[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(tr[x][0])PushDown(x),x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)Fa[x]=y;}//add in a new edge
void Cut(int x,int y){makeroot(x);if(findroot(y)==x&&Fa[y]==x&&!tr[y][0])Fa[y]=tr[x][1]=0,PushUp(x);}//delete a edge

int N,M;
int main()
{
    read(N),read(M);
    for(int i=1;i<=N;i++)read(v[i]);
    for(;M;M--){
        int Opt,x,y;read(Opt),read(x),read(y);
        switch(Opt){
            case 0:Split(x,y),printf("%d\n",s[y]);break;
            case 1:Link(x,y);break;
            case 2:Cut(x,y);break;
            case 3:Splay(x),v[x]=y;break;
        }
    }
}

HNOI2010弹飞绵羊

只有LinkCut

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=3e5+5,Size=1<<19;

int Fa[Maxn],tr[Maxn][2],s[Maxn],st[Maxn];
bool r[Maxn];

bool nroot(int x){return tr[Fa[x]][0]==x||tr[Fa[x]][1]==x;}
void PushUp(int x){s[x]=s[tr[x][0]]+s[tr[x][1]]+1;}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushDown(int x){
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[Fa[x]][1];}
void Rotate(int x){
    int y=Fa[x],z=Fa[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)Fa[w]=y;Fa[y]=x,Fa[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))st[++top]=y=Fa[y];
    while(top)PushDown(st[top--]);
    for(int S;S=Fa[x],nroot(x);Rotate(x))if(nroot(S))
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=Fa[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(tr[x][0])PushDown(x),x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)Fa[x]=y;}//add in a new edge
void Cut(int x,int y){makeroot(x);if(findroot(y)==x&&Fa[y]==x&&!tr[y][0])Fa[y]=tr[x][1]=0,PushUp(x);}//delete a edge

int N,M,A[Maxn];
int find(int x){return x+A[x]>N?N+1:x+A[x];}

int main()
{
    read(N);
    for(int i=1;i<=N;i++){
        read(A[i]);
        if(i+A[i]>N)Link(i,N+1);else Link(i,i+A[i]);
    }
    for(read(M);M;M--){
        int Opt,x,y;read(Opt),read(x),x++;
        switch(Opt){
            case 1:Split(x,N+1),printf("%d\n",s[N+1]-1);break;
            case 2:read(y),Cut(x,find(x)),A[x]=y,Link(x,find(x));break;
        }
    }
}

SDOI2008洞穴勘探

还是只有LinkCut

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=3e5+5,Size=1<<19;

int Fa[Maxn],tr[Maxn][2],s[Maxn],st[Maxn];
bool r[Maxn];

bool nroot(int x){return tr[Fa[x]][0]==x||tr[Fa[x]][1]==x;}
void PushUp(int x){s[x]=s[tr[x][0]]+s[tr[x][1]]+1;}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushDown(int x){
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[Fa[x]][1];}
void Rotate(int x){
    int y=Fa[x],z=Fa[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)Fa[w]=y;Fa[y]=x,Fa[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))st[++top]=y=Fa[y];
    while(top)PushDown(st[top--]);
    for(int S;S=Fa[x],nroot(x);Rotate(x))if(nroot(S))
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=Fa[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(tr[x][0])PushDown(x),x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)Fa[x]=y;}//add in a new edge
void Cut(int x,int y){makeroot(x);if(findroot(y)==x&&Fa[y]==x&&!tr[y][0])Fa[y]=tr[x][1]=0,PushUp(x);}//delete a edge

int N,M,A[Maxn];
int find(int x){return x+A[x]>N?N+1:x+A[x];}

int main()
{
    read(N);read(M);
    for(;M;M--){
        char Opt;int x,y;
        while((Opt=tc())<'A'||Opt>'Z');read(x),read(y);
        switch(Opt){
            case 'C':Link(x,y);break;
            case 'D':Cut(x,y);break;
            case 'Q':makeroot(x),puts(findroot(y)==x?"Yes":"No");break;
        }
    }
}

国家集训队Tree II

LCT维护懒标记(两个,加和乘),只要注意优先级就好了。

还有LinkCut和查询路径和。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

typedef long long LL;
const int Maxn=3e5+5,Size=1<<19,Mod=51061;

int Fa[Maxn],tr[Maxn][2],s[Maxn],st[Maxn],La[Maxn],Lm[Maxn],sz[Maxn],v[Maxn];
bool r[Maxn];

bool nroot(int x){return tr[Fa[x]][0]==x||tr[Fa[x]][1]==x;}
void PushUp(int x){s[x]=(s[tr[x][0]]+s[tr[x][1]]+v[x])%Mod;sz[x]=sz[tr[x][0]]+sz[tr[x][1]]+1;}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushAdd(int x,int c){s[x]+=(LL)c*sz[x]%Mod,s[x]%=Mod;La[x]+=c,La[x]%=Mod;v[x]+=c,v[x]%=Mod;}
void PushMul(int x,int c){Lm[x]=(LL)Lm[x]*c%Mod;La[x]=(LL)La[x]*c%Mod;s[x]=(LL)s[x]*c%Mod;v[x]=(LL)v[x]*c%Mod;}
void PushDown(int x){
    if(Lm[x]!=1)PushMul(tr[x][0],Lm[x]),PushMul(tr[x][1],Lm[x]),Lm[x]=1;
    if(La[x])   PushAdd(tr[x][0],La[x]),PushAdd(tr[x][1],La[x]),La[x]=0;
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[Fa[x]][1];}
void Rotate(int x){
    int y=Fa[x],z=Fa[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)Fa[w]=y;Fa[y]=x,Fa[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))st[++top]=y=Fa[y];
    while(top)PushDown(st[top--]);
    for(int S;S=Fa[x],nroot(x);Rotate(x))if(nroot(S))
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=Fa[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(tr[x][0])PushDown(x),x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)Fa[x]=y;}//add in a new edge
void Cut(int x,int y){makeroot(x);if(findroot(y)==x&&Fa[y]==x&&!tr[y][0])Fa[y]=tr[x][1]=0,PushUp(x);}//delete a edge

int N,M,A[Maxn];
int find(int x){return x+A[x]>N?N+1:x+A[x];}

int main()
{
    read(N);read(M);
    for(int i=1;i<=N;i++)sz[i]=v[i]=Lm[i]=1;
    for(int i=1,x,y;i<N;i++)read(x),read(y),Link(x,y);
    for(;M;M--){
        char Opt;while((Opt=tc())!='+'&&Opt!='-'&&Opt!='*'&&Opt!='/');
        int u,v,c;
        switch(Opt){
            case '+':read(u),read(v),read(c),Split(u,v),PushAdd(v,c);break;
            case '-':read(u),read(v),Cut(u,v),read(u),read(v),Link(u,v);break;
            case '*':read(u),read(v),read(c),Split(u,v),PushMul(v,c);break;
            case '/':read(u),read(v),Split(u,v),printf("%d\n",s[v]);break;
        }
    }
} 

NOI2014魔法森林

按最小生成树维护LCT即可。边权LCT不好维护,所以把边看成点共N+M个点即可。

#include <bits/stdc++.h>
using namespace std;

inline char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
inline void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}


const int Maxn=2e5+5;

int N,M,Ans=2e9;
struct Query{int x,y,a,b;}A[Maxn];
int Cmp(Query x,Query y){return x.a<y.a;}

int tr[Maxn][2],F[Maxn],mx[Maxn],r[Maxn],st[Maxn],v[Maxn];
bool nroot(int x){return tr[F[x]][0]==x||tr[F[x]][1]==x;}
void PushUp(int x){
    mx[x]=x;
    if(tr[x][0]&&v[mx[tr[x][0]]]>v[mx[x]])mx[x]=mx[tr[x][0]];
    if(tr[x][1]&&v[mx[tr[x][1]]]>v[mx[x]])mx[x]=mx[tr[x][1]];
}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushDown(int x){
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[F[x]][1];}
void Rotate(int x){
    int y=F[x],z=F[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;//details
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)F[w]=y;F[y]=x,F[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))st[++top]=y=F[y];
    while(top)PushDown(st[top--]);//details
    for(int S;S=F[x],nroot(x);Rotate(x))if(nroot(S))//details
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=F[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(tr[x][0])PushDown(x),x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)F[x]=y;}
void Cut(int x,int y){Split(x,y),F[x]=tr[y][0]=0,PushUp(y);}
int GetAns(int x,int y){Split(x,y);return mx[y];}

int Fa[Maxn];
int getf(int x){return x==Fa[x]?x:Fa[x]=getf(Fa[x]);}

int main()
{
    read(N),read(M);
    for(int i=1;i<=N+M;i++)Fa[i]=mx[i]=i;
    for(int i=1;i<=M;i++)
        read(A[i].x),read(A[i].y),read(A[i].a),read(A[i].b);
    sort(A+1,A+M+1,Cmp);
    for(int i=N+1;i<=N+M;i++)v[i]=A[i-N].b;
    for(int i=1;i<=M;i++){
        int x=A[i].x,y=A[i].y,a=A[i].a,b=A[i].b;
        if(getf(x)^getf(y)){
            Fa[getf(x)]=getf(y);
            Link(x,i+N),Link(i+N,y);
        }
        else{
            int k=GetAns(x,y);
            if(v[k]>A[i].b)
                Cut(A[k-N].x,k),Cut(k,A[k-N].y),Link(x,i+N),Link(i+N,y);
        }
        if(getf(1)==getf(N))
            Ans=min(Ans,a+v[GetAns(1,N)]);
    }printf("%d\n",Ans==2e9?-1:Ans);
}

WC2006水管局长

离线倒过来维护最小生成树。

细节巨多,注意最小生成树的优化。

#pragma GCC optimize(2) 
#include <bits/stdc++.h>
using namespace std;

inline char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
inline void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}

const int Maxn=1.1e6+5;

struct Edge{int x,y,c;}E[Maxn];
int Cmp(Edge x,Edge y){return x.c<y.c;}
int tr[Maxn][2],mx[Maxn],v[Maxn],r[Maxn],F[Maxn],st[Maxn];
bool nroot(int x){return tr[F[x]][0]==x||tr[F[x]][1]==x;}
void PushUp(int x){
    mx[x]=x;
    if(tr[x][0]&&v[mx[tr[x][0]]]>v[mx[x]])mx[x]=mx[tr[x][0]];
    if(tr[x][1]&&v[mx[tr[x][1]]]>v[mx[x]])mx[x]=mx[tr[x][1]];
}
void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
void PushDown(int x){
    if(r[x]){
        if(tr[x][0])PushRev(tr[x][0]);
        if(tr[x][1])PushRev(tr[x][1]);
        r[x]=0;
    }
}
int Getson(int x){return x==tr[F[x]][1];}
void Rotate(int x){
    int y=F[x],z=F[y],k=Getson(x),w=tr[x][k^1];
    if(nroot(y))tr[z][tr[z][1]==y]=x;//details
    tr[x][k^1]=y,tr[y][k]=w;
    if(w)F[w]=y;F[y]=x,F[x]=z;
    PushUp(y),PushUp(x);
}
void Splay(int x){
    int y=x,top=0;st[++top]=y;
    while(nroot(y))
        st[++top]=y=F[y];
    while(top)PushDown(st[top--]);//details
    for(int S;(S=F[x])&&nroot(x);Rotate(x))if(nroot(S))//details
        Rotate(Getson(x)==Getson(S)?S:x);
    PushUp(x);
}

void access(int x){for(int y=0;x;x=F[y=x])Splay(x),tr[x][1]=y,PushUp(x);}
void makeroot(int x){access(x),Splay(x),PushRev(x);}//in truely-tree
int findroot(int x){access(x),Splay(x);while(PushDown(x),tr[x][0])x=tr[x][0];Splay(x);return x;}//in truely-tree
void Split(int x,int y){makeroot(x),access(y),Splay(y);}//get the road
void Link(int x,int y){makeroot(x);if(findroot(y)^x)F[x]=y;}
//void Cut(int x,int y){makeroot(x);if(findroot(y)==x&&F[y]==x&&!tr[y][0]) F[y]=tr[x][1]=0,PushUp(x);}
void Cut(int x,int y){Split(x,y),F[x]=tr[y][0]=0,PushUp(x);} 

map<pair<int,int>,int>Pt;
int N,M,Q,Fa[Maxn],Ans[Maxn],Cpt,vis[Maxn];
int getf(int x){return x==Fa[x]?x:Fa[x]=getf(Fa[x]);}
struct Query{int Opt,x,y,dist;}Qr[Maxn];

int main()
{
    read(N),read(M),read(Q);
    for(int i=1;i<=M;i++){
        read(E[i].x),read(E[i].y),read(E[i].c);
        if(E[i].x>E[i].y)swap(E[i].x,E[i].y);
    }
    sort(E+1,E+M+1,Cmp);
    for(int i=1;i<=M;i++)Pt[make_pair(E[i].x,E[i].y)]=i;
    for(int i=1;i<=Q;i++){
        read(Qr[i].Opt),read(Qr[i].x),read(Qr[i].y);
        if(Qr[i].x>Qr[i].y)swap(Qr[i].x,Qr[i].y);
        if(Qr[i].Opt==2){
            Qr[i].dist=Pt[make_pair(Qr[i].x,Qr[i].y)];
            vis[Qr[i].dist]=1;
        }
    }
    for(int i=1;i<=N+M;i++)Fa[i]=i;
    for(int i=1;i<=M;i++)v[i+N]=E[i].c;
    for(int i=1,r=1;i<=M&&r<N;i++)if(!vis[i]){
        int x=getf(E[i].x),y=getf(E[i].y);
        if(x^y)Fa[x]=y,Link(E[i].x,i+N),Link(i+N,E[i].y),++r;//tips
    }
    for(int Qt=Q;Qt;Qt--){
        int x=Qr[Qt].x,y=Qr[Qt].y;
        if(Qr[Qt].Opt==1)
            Split(x,y),Ans[++Cpt]=v[mx[y]];
        else{
            Split(x,y);
            if(v[mx[y]]<=E[Qr[Qt].dist].c)continue;
            int k=mx[y];
            Cut(E[k-N].x,k),Cut(k,E[k-N].y);
            Link(x,Qr[Qt].dist+N);
            Link(Qr[Qt].dist+N,y);
        }

    }
    for(int i=Cpt;i;i--)printf("%d\n",Ans[i]);
}

ZJOI2016大森林

考试的时候看到题面就想起来看到过但没写过,具体写起来果然思考量还是很大。

考虑如果没有进行1操作,那么对于生长节点来说,接下来会有一些操作对其有影响。

再考虑是否能快速从第i棵树转移到第i+1棵树。

由于题目中是不存在删除操作的,那么可以说答案一但确定后就不会更改。

对于一个1操作来说,我们可以对其离线,转换成扫描线的形式。

我们考虑对1操作建一个虚点,对于1操作连到最近的另一个1操作。然后生长节点会长在虚点上。

对于1操作的一个左边界,我们将其连接到它应该去的地方(虚点及其下方挂的点)。即其真实的生长节点下。

对于1操作的一个右边界,我们将其连接回原来点到的虚点。虚点之间连边是为了保证查询路径时树联通且可以统计影响。

那么对于虚点其点权为0否则为1。所以我们求路径时需要求LCA

由于这道题建立了虚点,且树的形态是固定的,所以我们不能直接makeroot

#include <cstdio>
#include <algorithm>
using namespace std;

inline char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
inline void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}

const int Maxn=2e5+5;

struct Events{
    int Pos,t,x,y;
    bool operator<(const Events&P)const{
        return Pos<P.Pos||(Pos==P.Pos&&t<P.t);
    }
}G[Maxn<<2];

namespace LCT{
    #define MaxS 400005
    int tr[MaxS][2],F[MaxS],r[MaxS],s[MaxS],v[MaxS],st[MaxS];
    #undef MaxS
    int nroot(int x){return tr[F[x]][0]==x||tr[F[x]][1]==x;}
    int GetSon(int x){return tr[F[x]][1]==x;}
    void PushUp(int x){s[x]=s[tr[x][0]]+s[tr[x][1]]+v[x];}
    void PushRev(int x){swap(tr[x][0],tr[x][1]),r[x]^=1;}
    void PushDown(int x){
        if(r[x]){
            if(tr[x][0])PushRev(tr[x][0]);
            if(tr[x][1])PushRev(tr[x][1]);
            r[x]=0;
        }
    }
    void Rotate(int x){
        int y=F[x],z=F[y],k=GetSon(x),w=tr[x][k^1];
        if(nroot(y))tr[z][tr[z][1]==y]=x;
        tr[y][k]=w,tr[x][k^1]=y;
        if(w)F[w]=y;F[x]=z,F[y]=x;
        PushUp(y),PushUp(x);
    }
    void Splay(int x){
        int top=0,y=x;st[++top]=y;
        while(nroot(y))st[++top]=y=F[y];
        while(top)PushDown(st[top--]);
        for(int S;S=F[x],nroot(x);Rotate(x))if(nroot(S))
            Rotate(GetSon(x)==GetSon(S)?S:x);
        PushUp(x);
    }
    int access(int x,int y=0){for(;x;x=F[y=x])Splay(x),tr[x][1]=y,PushUp(x);return y;}
    void Link(int x,int y){Splay(x),F[x]=y;}
    void Cut(int x){access(x),Splay(x),tr[x][0]=F[tr[x][0]]=0,PushUp(x);}
    //因为树的形态是固定的,所以只需要cut其父亲即可
    int Query(int x,int y,int res=0){
        access(x),Splay(x),res=s[x];
        int fa=access(y);Splay(y);
        res+=s[y];access(fa),Splay(fa);res-=s[fa]<<1;return res;
    }//求LCA:x的access是将虚边打通成实边,那么y遇到的第一个实边的下方的端点就是其LCA
}

int N,M,Opt,L,R,u,id[Maxn<<1],Cnt,Cnt_Rl,lst;
int l[Maxn<<1],r[Maxn<<1],Pnt,Qnt,Ans[Maxn];
int main()
{
    read(N),read(M),Cnt_Rl=id[1]=LCT::v[1]=l[1]=1,lst=Cnt=2,r[1]=N;
    LCT::Link(Cnt,1);
    for(int i=1;i<=M;i++){
        read(Opt);
        switch(Opt){
            case 0:
                read(L),read(R),LCT::v[id[++Cnt_Rl]=++Cnt]=1;
                LCT::Link(Cnt,lst),l[Cnt_Rl]=L,r[Cnt_Rl]=R;
                break;
            case 1:
                read(L),read(R),read(u);
                L=max(L,l[u]),R=min(R,r[u]);//消除节点不存在的影响
                if(L>R)continue;
                LCT::Link(++Cnt,lst);
                G[++Pnt]=(Events){L,i-M,Cnt,id[u]};
                G[++Pnt]=(Events){R+1,i-M,Cnt,lst};
                lst=Cnt;
                break;
            case 2:
                read(L),read(R),read(u);
                G[++Pnt]=(Events){L,++Qnt,id[R],id[u]};
                break;
        }
    }
    sort(G+1,G+Pnt+1);
    for(int i=1;i<=Pnt;i++){
        if(G[i].t>0)Ans[G[i].t]=LCT::Query(G[i].x,G[i].y);
        else LCT::Cut(G[i].x),LCT::Link(G[i].x,G[i].y);
    }
    for(int i=1;i<=Qnt;i++)printf("%d\n",Ans[i]);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*