题目传送门
每个询问其实是求前面有多少个区间与之相交
答案就是：前面区间数量-与前面区间不相交数量
与前面区间不相交数量=前面区间 l 大于询问 r 的数量 + 前面区间 r 小于询问 l 的数量
代码：
#include<cstdio>
using namespace std;#define low(x) (x&(-x))
const int maxn=50000+100;int treel[maxn],treer[maxn];
int n,m;void Add(int *tree,int x){while(x<=n){tree[x]++;x+=low(x); }
}int GetSum(int *tree,int x){int sum=0;while(x){sum+=tree[x];x-=low(x);}return sum;
}int main(){scanf("%d%d",&n,&m);int type,l,r;int typeonenum=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&type,&l,&r);if(type==2) printf("%d\n",typeonenum-GetSum(treel,n)+GetSum(treel,r)-GetSum(treer,l-1));if(type==2) continue;else typeonenum++;Add(treel,l);Add(treer,r);}
}