题目链接：https://loj.ac/problem/10115
题目描述
原题来自：Vijos P1448
校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：
- K=1，读入l,r 表示在l 到 r 之间种上一种树，每次操作种的树的种类都不同；
- K=2，读入 l,r 表示询问 l 到 r 之间有多少种树。
注意：每个位置都可以重复种树。
输入格式
第一行 表示道路总长为 n，共有 m个操作；
接下来 m 行为 m 个操作。
输出格式
对于每个 K=2 输出一个答案。
样例
样例输入
5 4
1 1 3
2 2 5
1 2 4
2 3 5
样例输出
1
2
解题思路:开始怎么想都不知道怎么维护不同段中树的种类是否相同的情况，感觉这题有个思维技巧还是挺难想的，就是我们要开两个数组，sum1分别维护左端点的数目，另一个数组sum2维护右端点的数目。这样区间[l,r]的树的种类的数目就是1-r中左端点的数目减去1-(l-1)中右端点的数目，即表示为sum1[r]-sum2[l-1]。
如图假如我们第一次在区间a[2,6]种上一种树，然后再在区间b[5,10]种上一种树，这时我们要统计区间c[8,12]中树的种类数目，我们就统计[1,12]中左端点的数目即 sum1[12]等于2，说明有两种树可能在给定区间内，然后我们再求区间[1,7]中右端点的数目即sum2[7-1]=1,表示有一种树完全在给定区间左边，并不是我们要求的，所以减去就好了，所以答案就为sum1[12]-sum2[7-1]了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<queue>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn=5e4+;
int n,m,k,l,r,sum1[maxn],sum2[maxn];
//sum1[i]表示的是区间[1,i]中左端点的数目,sum2[i]表示的是区间[1,i]右端点的数目；
int lowbit(int x){return x&(-x);}
void update1(int x,int val){ //更新左端点的数目
while(x<=maxn){
sum1[x]+=val;
x+=lowbit(x);
}
}
void update2(int x,int val){ //更新右端点的数目
while(x<=maxn){
sum2[x]+=val;
x+=lowbit(x);
}
}
int ask1(int x){ //查找区间[1,x]中左端点的数目
int res=;
while(x){
res+=sum1[x];
x-=lowbit(x);
}
return res;
}
int ask2(int x){ //查找区间[1,x]中右端点的数目
int res=;
while(x){
res+=sum2[x];
x-=lowbit(x);
}
return res;
}
int main(){
cin>>n>>m;
while(m--){
cin>>k>>l>>r;
if(k==){
update1(l,); update2(r,);
}else{
cout<<ask1(r)-ask2(l-)<<endl;
}
}
return ;
}