C++(clang++ 11.0.1) 解法, 执行用时: 351ms, 内存消耗: 10000K, 提交时间: 2022-10-02 14:31:36

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 1000010
using namespace std;
int n,m,c=1,now=0,top=0;
int s[MAXN],t[MAXN],w[MAXN],ans[MAXN];
bool used[MAXN];
struct Link_Cut_Tree{
    int size,stack[MAXN];
    struct node1{
        int son[2];
        int f,v,s,flag;
    }a[MAXN];
    inline bool isroot(int rt){
        return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
    }
    inline void newnode(int x){
        int rt=++size;
        a[rt].s=a[rt].v=x;
    }
    inline void pushup(int rt){
        if(!rt)return;
        a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+a[rt].v;
    }
    inline void pushdown(int rt){
        if(!rt||!a[rt].flag)return;
        a[a[rt].son[0]].flag^=1;a[a[rt].son[1]].flag^=1;a[rt].flag^=1;
        swap(a[rt].son[0],a[rt].son[1]);
    }
    inline void turn(int rt){
        int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
        if(!isroot(x)){
            if(a[y].son[0]==x)a[y].son[0]=rt;
            else a[y].son[1]=rt;
        }
        a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
        a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
        pushup(x);pushup(rt);
    }
    void splay(int rt){
        int top=0;
        stack[++top]=rt;
        for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;
        while(top)pushdown(stack[--top]);
        while(!isroot(rt)){
            int x=a[rt].f,y=a[x].f;
            if(!isroot(x)){
                if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);
                else turn(x);
            }
            turn(rt);
        }
    }
    void access(int rt){
        for(int i=0;rt;i=rt,rt=a[rt].f){
            splay(rt);
            a[rt].son[1]=i;
            pushup(rt);
        }
    }
    int access_lca(int rt){
        int i;
        for(i=0;rt;i=rt,rt=a[rt].f){
            splay(rt);
            a[rt].son[1]=i;
            pushup(rt);
        }
        return i;
    }
    inline void split(int x){access(x);splay(x);}
    inline void link(int x,int y){splay(x);a[x].f=y;}
    inline void cut(int x){split(x);a[a[x].son[0]].f=0;a[x].son[0]=0;pushup(x);}
}LCT;
struct node2{
    int id,f,x,y;
}a[MAXN];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
bool cmp(const node2 &x,const node2 &y){
    if(x.id==y.id)return x.f<y.f;
    return x.id<y.id;
}
inline void add(int id,int f,int x,int y){
    top++;
    a[top].id=id;a[top].f=f;a[top].x=x;a[top].y=y;
}
void work(){
    int x,y,lca;
    for(int i=1,k=1;i<=n;i++)
    for(;a[k].id==i;k++){
        int t=a[k].f;
        if(t>0){
            x=a[k].x;y=a[k].y;
            LCT.split(x);ans[t]+=LCT.a[x].s;
            lca=LCT.access_lca(y);LCT.splay(y);ans[t]+=LCT.a[y].s;
            LCT.split(lca);ans[t]-=LCT.a[lca].s*2;
        }
        else{
            LCT.cut(a[k].x);LCT.link(a[k].x,a[k].y);
        }
    }
    for(int i=1;i<=m;i++)if(used[i])printf("%d\n",ans[i]);
}
void init(){
    int f,x,y,k;
    n=read();m=read();
    LCT.newnode(1);LCT.newnode(0);LCT.link(2,1);
    now=2;
    w[1]=s[1]=1;t[1]=n;
    for(int i=1;i<=m;i++){
        f=read();x=read();y=read();
        if(f==0){
            c++;
            LCT.newnode(1);
            w[c]=LCT.size;s[c]=x;t[c]=y;
            add(1,i-m,LCT.size,now);
        }
        if(f==1){
            k=read();x=max(x,s[k]);y=min(y,t[k]);
            if(x<=y){
                LCT.newnode(0);LCT.link(LCT.size,now);
                add(x,i-m,LCT.size,w[k]);
                add(y+1,i-m,LCT.size,now);
                now=LCT.size;
            }
        }
        if(f==2){
            k=read();
            used[i]=true;
            add(x,i,w[y],w[k]);
        }
    }
    sort(a+1,a+top+1,cmp);
}
int main(){
    init();
    work();
	return 0;
}