树状数组
我们开两个权值树状数组 $tl,tr$，分别存储布雷的左、右边界。
那么对于给定区间 $[l,r]$，答案即 $tl.query(r)-tr.query(l-1)$。
如图：
蓝色即布雷区间，黑色即查询区间。
$\color{black}\colorbox{black}{1}$ 黑色右区间之前的 $\color{skyblue}\colorbox{skyblue}{1}$ 蓝色左边界所在区间才有可能与 $\color{black}\colorbox{black}{1}$ 黑色区间重合。
那么我们再减去 $\color{black}\colorbox{black}{1}$ 黑色区间左边界左边的 $\color{skyblue}\colorbox{skyblue}{1}$ 蓝色左边界数量（未重合）即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5;
struct tree{
int t[N+1];
int lowbit(int x){
return x&-x;
}
void add(int x,int k){
while(x<=N){
t[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}return ans;
}
}tl,tr;
int n,m;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
while(m--){
int q,l,r;
scanf("%d %d %d",&q,&l,&r);
switch(q){
case 1:
tl.add(l,1);tr.add(r,1);
break;
case 2:
printf("%d\n",tl.query(r)-tr.query(l-1));
break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
