传送门
【题目分析】
考虑每次是在区间[l,r]中埋一种，所以记录每次的左右端点，查询一段区间[l,r]就是统计1~r中埋了多少雷，再减去1~l-1中埋完的雷（即右端点）即可。
所以用两个树状数组维护左右端点信息即可。（常数比线段树要小）
【代码~】
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const int MOD=1e6;
int n,q;
int tr1[MAXN],tr2[MAXN];
int Read(){
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
int lowbit(int x){
return x&(-x);
}
void update(int x,int y,int v){
for(int i=x;i<=n;i+=lowbit(i))
tr1[i]+=v;
for(int i=y;i<=n;i+=lowbit(i))
tr2[i]+=v;
}
int query(int x,int y){
int ret=0;
for(int i=y;i;i-=lowbit(i))
ret+=tr1[i];
for(int i=x;i;i-=lowbit(i))
ret-=tr2[i];
return ret;
}
int main(){
n=Read(),q=Read();
while(q--){
int cz=Read(),l=Read(),r=Read();
if(cz==1)
update(l,r,1);
else
printf("%d\n",query(l-1,r));
}
return 0;
}
