题目链接
思路
树状数组的模板题
1.只要一个区间的开头在一个节点(i)的左边，那么这个区间包含在区间(1~i)中。
2.只要一个区间的尾部在一个节点(j)的左边，那么这个区间肯定不属于(j)之后的所有区间
所以我们可以搞两个树状数组来做
(tree_{head}[i])维护(i)之前的开头数量
(tree_{tail}[j])维护(j)之前的结尾数量
结合样例可以看出来(tree_{head}[j]-tree_{tail}[i])即为i-j之间的雷种类数
样例分析:
5 4
1 1 3
2 2 5
1 2 4
2 3 5
1
2
假设要求2到3之间的雷种类数,可以看出(tree_{tail}[1]=0),(head_{tail}[3]=2),
所以上述的结论成立
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
#define lowbit(x) x & -x
#define N 100000
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int head_tree[N*2],tail_tree[N*2],n,m;
void update_head(int x) {
while(x<=n) {
++head_tree[x];
x+=lowbit(x);
}
}
void update_tail(int x) {
while(x<=n) {
++tail_tree[x];
x+=lowbit(x);
}
}
int find_head(int x) {
int res=0;
while(x>0) {
res+=head_tree[x];
x-=lowbit(x);
}
return res;
}
int find_tail(int x) {
int res=0;
while(x>0) {
res+=tail_tree[x];
x-=lowbit(x);
}
return res;
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; ++i) {
int q,x,y;
cin>>q>>x>>y;
if(q==1) {
update_head(x);
update_tail(y);
} else {
cout<<find_head(y)-find_tail(x-1)<<"
";
}
}
return 0;
}