P2184 贪婪大陆
题目链接
思路
树状数组的模板题
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)<<"\n";
}
}
return 0;
}
版权声明：本文为pyyyyyy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。