校門外的樹
【題目分析】題目描述的是一種區間修改，看起來好像要用線段樹。但是對于這種區間內部沒有差別并且查詢的是區間內的類別的問題，是可以轉化為樹狀數組進行的。畢竟樹狀數組更加簡單。
我們的關注點應該放在區間的端點處，然后通過統計端點得到答案。
我們不妨用數組a1保存左端點的個數，用數組a2保存右端點的個數（從開始到x）假如查詢的是區間[l,r]，那么a1[r]是區間[1,r]的種類數，a2[l-1]是區間[1,r]中不包含在[l,r]的種類數，答案就是a1[r]-a1[l-1]
代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int n,m,k,l,r;
const int MAXN=50005;
int a1[MAXN],a2[MAXN];int lowbit(int x)
{return x&(-x);
}void update1(int x,int y)
{while(x<=n){a1[x]+=y;x+=lowbit(x);}
}
void update2(int x,int y)
{while(x<=n){a2[x]+=y;x+=lowbit(x);}
}int ask1(int x)
{int ret=0;while(x){ret+=a1[x];x-=lowbit(x);}return ret;
}
int ask2(int x)
{int ret=0;while(x){ret+=a2[x];x-=lowbit(x);}return ret;
}int main()
{scanf("%d%d",&n,&m);memset(a1,0,sizeof(a1));memset(a2,0,sizeof(a2));for(int i=0;i<m;i++){scanf("%d%d%d",&k,&l,&r);if(k==1){update1(l,1);update2(r,1);}else if(k==2){printf("%d\n",ask1(r)-ask2(l-1));}}return 0;
}