ref不是太懂……
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, tot, val[200005], fa[200005], idx[200005], num, lf[200005], cnt;
int ans[200005], ch[200005][2], sum[200005], rg[200005], opt, uu, vv, ww;
struct Node{
int pos, idx, u, v;
bool operator<(const Node &x)const{
if(pos!=x.pos) return pos<x.pos;
return idx<x.idx;
}
}nd[400005];
int getW(int x){
return ch[fa[x]][1]==x;
}
void upd(int x){
sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
}
bool isRoot(int x){
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
void rotate(int x){
int old=fa[x], oldf=fa[old], w=getW(x);
if(!isRoot(old)) ch[oldf][ch[oldf][1]==old] = x;
ch[old][w] = ch[x][w^1]; ch[x][w^1] = old;
fa[ch[x][w^1]] = x; fa[ch[old][w]] = old; fa[x] = oldf;
upd(old); upd(x);
}
void splay(int x){
while(!isRoot(x)){
int f=fa[x];
if(!isRoot(f)) rotate(getW(f)==getW(x)?f:x);
rotate(x);
}
upd(x);
}
int access(int x){
int y=0;
while(x){
splay(x);
ch[x][1] = y;
upd(x);
y = x;
x = fa[x];
}
return y;
}
void cut(int x){
access(x);
splay(x);
fa[ch[x][0]] = 0;
ch[x][0] = 0;
upd(x);
}
int main(){
cin>>n>>m;
val[1] = lf[1] = tot = num = idx[1] = 1;
rg[1] = n;
fa[++tot] = 1;
int now=tot;
for(int i=1; i<=m; i++){
scanf("%d", &opt);
if(!opt){
scanf("%d %d", &uu, &vv);
val[++tot] = 1; idx[++num] = tot; lf[num] = uu; rg[num] = vv;
fa[tot] = now;
}
else if(opt==1){
scanf("%d %d %d", &uu, &vv, &ww);
uu = max(uu, lf[ww]); vv = min(vv, rg[ww]);
if(uu>vv) continue;
fa[++tot] = now;
nd[++cnt] = (Node){uu, i-m, tot, idx[ww]};
nd[++cnt] = (Node){vv+1, i-m, tot, now};
now = tot;
}
else{
scanf("%d %d %d", &ww, &uu, &vv);
nd[++cnt] = (Node){ww, i, idx[uu], idx[vv]};
}
}
sort(nd+1, nd+1+cnt);
int k=1;
memset(ans, -1, sizeof(ans));
for(int i=1; i<=n; i++){
for(; k<=cnt && nd[k].pos==i; k++){
if(nd[k].idx<=0){
cut(nd[k].u);
fa[nd[k].u] = nd[k].v;
}
else{
access(nd[k].u); splay(nd[k].u); int qwq=sum[nd[k].u];
int t=access(nd[k].v); splay(nd[k].v); qwq += sum[nd[k].v];
access(t); splay(t); qwq -= sum[t] << 1;
ans[nd[k].idx] = qwq;
}
}
}
for(int i=1; i<=m; i++)
if(ans[i]>=0)
printf("%d
", ans[i]);
return 0;
}