Description：

有 $n$ 棵树排成一排，三种操作：

$0$ $l$ $r$ 表示第 $l$ 到第 $r$ 棵树的生长节点下面长出一个子节点。

$1$ $l$ $r$ $x$ 表示第 $l$ 棵树到第 $r$ 棵树的生长节点改到标号为 $x$ 的节点。

$2$ $x$ $u$ $v$ 表示询问第 $x$ 棵树中 $u$ 到 $v$ 的距离。

$1\leqslant n\leqslant10^5,1\leqslant m\leqslant 2\times 10^5$

Solution：

首先一个最暴力的想法是每棵树维护一个 $LCT$ ，然后在上面做，树上求距离还可以用树上差分。

但是这样显然是不行的，考虑将操作离线，每次维护当前 $LCT$ 的形态，那么发现一次 $1$ 操作只不过会把这一段区间新长出来的点移动到 $x$ 下面，那么我们可以建立一个虚点，然后到 $r$ 的时候再把虚点还有所有接在它上的点都接回去，然后就可以维护了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

struct node

{

	int c[2],fa;

	int val,sum;

}t[MAXN];

int ptr = 0;

int num[MAXN],realtot = 0;

int newnode(int w){++ptr;t[ptr].val = t[ptr].sum = w;return ptr;}

void maintain(int rt){t[rt].sum = t[t[rt].c[0]].sum + t[t[rt].c[1]].sum + t[rt].val;return;}

bool isroot(int rt){return (t[t[rt].fa].c[0] != rt && t[t[rt].fa].c[1] != rt);}

int id(int rt){return (t[t[rt].fa].c[0] == rt ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

void splay(int x)

{

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		else if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

int access(int k){int i = 0;for(;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return i;}

void link(int k,int f){access(k);splay(k);t[k].fa = f;return;}

void cut(int k){access(k);splay(k);t[t[k].c[0]].fa = 0;t[k].c[0] = 0;maintain(k);return;}

struct option

{

	int pos,tim,type,a,b,ans;

	//type 1 : cut a from his father,link a to b

	//type 2 : query dist between a and b

	//opt 1 : link a to b at pos l,cut a from his father at pos r + 1

	//opt 2 : link virtual point v to cur growpoint

	//        link virtual point v to new grwopoint at pos l

	//        link virtual point v to pre growpoint at at pos r + 1

	//opt 3 : query dist between a and b

}s[MAXN << 1];

int optcnt = 0;

bool cmp_option(option a,option b){return (a.pos == b.pos ? a.tim < b.tim : a.pos < b.pos);}

bool cmp_tim(option a,option b){return a.tim < b.tim;}

int lef[MAXN],rig[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int opt,l,r,x,u,v;

	num[++realtot] = newnode(1);

	newnode(0);link(2,1);

	lef[1] = 1;rig[1] = n;

	int growpoint = 2;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 0)

		{

			scanf("%d%d",&l,&r);

			num[++realtot] = newnode(1);

			lef[realtot] = l;rig[realtot] = r;

			s[++optcnt] = (option){l,i,1,num[realtot],growpoint};

			s[++optcnt] = (option){r + 1,i,1,num[realtot],0};

		}

		if(opt == 1)

		{

			scanf("%d%d%d",&l,&r,&x);

			l = max(l,lef[x]);r = min(r,rig[x]);

			if(l > r)continue;

			int v = newnode(0);

			link(v,growpoint);

			s[++optcnt] = (option){l,i,1,v,num[x]};

			s[++optcnt] = (option){r + 1,i,1,v,growpoint};

			growpoint = v;

		}

		if(opt == 2)

		{

			scanf("%d%d%d",&x,&u,&v);

			s[++optcnt] = (option){x,i + m,2,num[u],num[v]};

		}

	}

	sort(s + 1,s + 1 + optcnt,cmp_option);

	for(int i = 1;i <= optcnt;++i)

	{

		if(s[i].type == 1)

		{

			cut(s[i].a);link(s[i].a,s[i].b);

		}

		else

		{

			int res = 0;

			access(s[i].a);splay(s[i].a);res += t[s[i].a].sum;

			int lca = access(s[i].b);splay(s[i].b);res += t[s[i].b].sum;

			access(lca);splay(lca);res -= 2 * t[lca].sum;

			s[i].ans = res;

		}

	}

	sort(s + 1,s + 1 + optcnt,cmp_tim);

	for(int i = 1;i <= optcnt;++i)

	{

		if(s[i].type == 2)printf("%d\n",s[i].ans);

	}

	return 0;

}