线段树维护区间并

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
int T,n,q,a[50005],b[50005];
long long ot;
struct node {
	long long x,y;
};
typedef vector<node> V;
V ans,v[200005];
void add(V &re,node &now,node pl) {
	if(pl.x>now.y+1) {
		if(now.y>=0) re.push_back(now);
		now=pl;
	} else now.y=max(now.y,pl.y);
}
V pt(V vt,node wt) {
	for (int i=0;i<vt.size();i++) {
		vt[i].x+=wt.x;
		vt[i].y+=wt.y;
	}
	return vt;
}
V gt(const V &a,const V &b) {
	V re;
	int i=0,j=0;
	node now=(node) {
		0,-1
	}
	;
	while(i<a.size()&&j<b.size()) {
		if(a[i].x<b[j].x) add(re,now,a[i++]); else add(re,now,b[j++]);
	}
	while(i<a.size()) add(re,now,a[i++]);
	while(j<b.size()) add(re,now,b[j++]);
	re.push_back(now);
	return re;
}
V merge(const V &a,const V &b) {
	if(!a.size()) return b;
	if(!b.size()) return a;
	V c=a;
	for (int i=0;i<b.size();i++) c=gt(c,pt(a,b[i]));
	return c;
}
void build(int k,int l,int r) {
	if(l==r) {
		v[k].clear();
		v[k].push_back((node) {0,0});
		v[k].push_back((node) {a[l],b[l]});
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	v[k]=merge(v[lc],v[rc]);
}
void ch(int k,int l,int r,int x) {
	if(l==r&&l==x) {
		v[k].clear();
		v[k].push_back((node) {0,0});
		v[k].push_back((node) {a[l],b[l]});
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x); else ch(rc,mid+1,r,x);
	v[k]=merge(v[lc],v[rc]);
}
void find(int k,int l,int r,int x,int y) {
	if(l>=x&&r<=y) {
		ans=merge(ans,v[k]);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) find(lc,l,mid,x,y);
	if(y>mid) find(rc,mid+1,r,x,y);
}
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&q);
		for (int i=1;i<=n;i++) {
			scanf("%d%d",&a[i],&b[i]);
		}
		build(1,1,n);
		int tp,x,y;
		while(q--) {
			scanf("%d",&tp);
			if(tp==1) {
				scanf("%d",&x);
				scanf("%d%d",&a[x],&b[x]);
				ch(1,1,n,x);
			} else {
				scanf("%d%d",&x,&y);
				ans.clear();
				find(1,1,n,x,y);
				ot=0;
				for (int i=0;i<ans.size();i++) {
					ot+=ans[i].y-ans[i].x+1;
				}
				printf("%lld\n",ot);
			}
		}
	}
	return 0;
}