千万别用树套树

一道好题，我们计算包含这个区间的线段很难计算，离线也不行，于是我们用到了容斥的原理，用总的线段减去不在这个区间的线段。

一条线段没有包含这个区间有两种情况：

  1. 线段右端点在当前区间的右端点的左边
  2. 线段的左端点在当前区间左端点的右边

于是我们分别统计这两种线段的个数即可。

对于第一种情况，我们需要记录右端点的信息，我们用一个树状数组每次填充1到右端点即可，最后就能根据数字查询了。
对于第二种情况，我们记录左端点的信息，每次从1填充到左端点即可

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e5+10;
int n,q,t[N][2],res;
inline void add(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i))	t[i][k]+=1;	
}
inline int ask(int x,int k){
	int res=0; for(int i=x;i;i-=lowbit(i))	res+=t[i][k]; return res;
}
signed main(){
	while(~scanf("%d %d",&n,&q)){
		memset(t,0,sizeof t);	res=0;
		while(q--){
			int op,l,r;	scanf("%d %d %d",&op,&l,&r);
			if(op==1)	res++,add(l,1),add(r,2);
			else	printf("%d\n",res-ask(r-1,2)-ask(n,1)+ask(l,1));
		}
	}
	return 0;
}