猫史档案馆

题目描述

小 Y 家里有一个大森林，里面有 nn 棵树，编号从 11 到 nn。一开始这些树都只是树苗，只有一个节点，标号为 11。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。

小 Y 掌握了一种魔法，能让第 ll 棵树到第 rr 棵树的生长节点长出一个子节点。同时她还能修改第 ll 棵树到第 rr 棵树的生长节点。她告诉了你她使用魔法的记录，你能不能管理她家的森林，并且回答她的询问呢？

输入格式

第一行包含 22 个正整数 n,mn,m，共有 nn 棵树和 mm 个操作。

接下来 mm 行，每行包含若干非负整数表示一个操作，操作格式为：

0 l r 表示将第 ll 棵树到第 rr 棵树的生长节点下面长出一个子节点，子节点的标号为上一个 00 号操作叶子标号加 11（例如，第一个 00 号操作产生的子节点标号为 22）， ll 到 rr 之间的树长出的节点标号都相同。保证 1\leq l\leq r\leq n1≤l≤r≤n 。

1 l r x 表示将第 ll 棵树到第 rr 棵树的生长节点改到标号为 xx 的节点。对于 ii (l\leq i\leq rl≤i≤r) 这棵树，如果标号 xx 的点不在其中，那么这个操作对该树不产生影响。保证 1\leq l\leq r\leq n1≤l≤r≤n，xx 不超过当前所有树中节点最大的标号。

2 x u v 询问第 xx 棵树中节点 uu 到节点 vv 点的距离，也就是在第 xx 棵树中从节点 uu 和节点 vv 的最短路上边的数量。保证 1\leq x\leq n1≤x≤n，这棵树中节点 uu 和节点 vv 存在。

输出格式

输出包括若干行，按顺序对于每个小 Y 的询问输出答案。

输入输出样例 输入 #1<button class="copy-btn lfe-form-sz-middle" type="button" data-v-370e72e2="" data-v-52f2d52f="">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" type="button" data-v-370e72e2="" data-v-52f2d52f="">复制</button>

1
2

说明/提示

对于 100\%100% 的数据，N\leq 10^5,M\leq 2\times 10^5N≤105,M≤2×105。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define R RG int
#define I inline
#define G ch=getchar()
#define lc c[x][0]
#define rc c[x][1]
#define qr(P,O,X,Y) qry[++q]=(QRY){P,O,X,Y}
using namespace std;
const int N=300009;
struct QRY{//封结构体，把嫁接和询问按顺序排序
    int pos,ord,x,y;
    I bool operator<(RG QRY a)const{
        return pos<a.pos||(pos==a.pos&&ord<a.ord);
    }
}qry[N];
int f[N],c[N][2],s[N],gl[N],gr[N],at[N],ans[N];
bool v[N];
I void in(R&x){
    register char G;
    while(ch<'-')G;
    x=ch&15;G;
    while(ch>'-')x*=10,x+=ch&15,G;
}
I bool nrt(R x){return c[f[x]][0]==x||c[f[x]][1]==x;}
I void up(R x){s[x]=s[lc]+s[rc]喵[x];}
I void rot(R x){
    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
    if(nrt(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
    up(f[w]=y);f[y]=x;f[x]=z;
}
I void sp(R x){
    for(R y;nrt(x);rot(x))
        if(nrt(y=f[x]))rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
    up(x);
}
I int ac(R x){R y=0;while(x)sp(x),rc=y,up(y=x),x=f[x];return y;}
I void ct(R x){ac(x);sp(x);lc=f[lc]=0;up(x);}
I void lk(R x,R y){sp(x);f[x]=y;}//蒟蒻的LCT越写越丑了。。。
int main(){
    R q=0,tot=0,n,m,p,real,aux,i,op,l,r,x,y;
    in(n);in(m);
    real=v[1]=s[1]=at[1]=gl[1]=1;gr[1]=n;
    lk(p=aux=2,1);//一开始也要来一个虚点
    for(i=1;i<=m;++i){
        in(op);in(l);in(r);
        if(op==0){//默认一开始全长在一起
            lk(at[++real]=++p,aux);v[p]=s[p]=1;
            gl[real]=l;gr[real]=r;
        }//gl和gr方便下面把无用的区间去掉
        else if(op==1){//有些区间连这个点都没长出来，直接取min，max
            in(x);l=max(l,gl[x]);r=min(r,gr[x]);
            if(l>r)continue;
            lk(++p,aux);
            qr(l,i-m,p,at[x]);qr(r+1,i-m,p,aux);//-m是为了把所有嫁接放到询问之前
            aux=p;//更新生长节点位置
        }
        else in(x),qr(l,++tot,at[r],at[x]);
    }
    sort(qry+1,qry+q+1);
    for(i=1;i<=q;++i){
        if(qry[i].ord>0){
              ac(x=qry[i].x);sp(x);r=s[x];
            l=ac(y=qry[i].y);sp(y);r+=s[y];
              ac(l);ans[qry[i].ord]=r-(s[l]<<1);//差分一下
        }
        else ct(qry[i].x),lk(qry[i].x,qry[i].y);
    }
    for(i=1;i<=tot;++i)printf("%d\n",ans[i]);
    return 0;
}

猫史档案馆

P3348 [ZJOI2016]大森林【c++】

回复