题目大意:
支持两种操作,区间添加一种新元素,查询区间颜色种数..
题目标签是线段树啊,我也本来想写一个线段树,后来写不出来……(我太弱了orz)
然后就草率地看了看题解里面的思路咯,感觉思路非常的不错,于是我就A掉这题之后写了这篇blog…
我们通过这幅图可以看到:
- 我们直接统计区间的覆盖不是很好统计, 考虑前缀
- 当前我们已经进行了10次覆盖
- 从[1,R]这个区间中有9个覆盖
- 但是其中有3个覆盖完全在L的左侧(即右端点在[1,L-1])
- 所以应该只有6次覆盖在[L,R]范围内
- ∴ans=6
我们可以发现,这是一个区间覆盖的问题,询问的答案是[1,r]中的种类数减去[1,l-1] 中的右端点数…
然后此题就沦为了一道区间和单点修改单点和区间查询的题目…
我们可以用两个不同的数据结构来分别维护右端点数目和种类数…我们整理了一下发现:
- 对于右端点,我们修改的时候在右端点单点加,查询的时候区间查询[1,l-1]..
- 对于种类数,我们修改的时候做区间加,往区间[l,n]加上,查询的时候单点查 r点的值..
所以,一个单点加区间查,一个区间加单点查,就是这样两个树状数组的基本操作了…
而区间操作都是含1和n的,所以我们就可以省掉一些步骤..
最后写出来就是这样:
#include <cstdio>
const int N=101010;
inline int gnum(){
int a=0;char c=getchar();for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar()) a=(a<<1)+(a<<3)+c-'0'; return a;
}
int t[2][N],n,m;
void add(int *c,int x){for(;x<=n;x+=x&-x)++c[x];}
int query(int *c,int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;}
int main(){
n=gnum(),m=gnum();
for(int i=1;i<=m;++i){
int o=gnum(),l=gnum(),r=gnum();
//端点:单点r加1 区间1..l-1查
//种类:区间l..n加1 单点r查
if(o-2) add(t[0],l),add(t[1],r);
else printf("%d
",query(t[0],r)-query(t[1],l-1));
}
}这样就可以咯~