P1972 [SDOI2009] HH的项链
题意概括：
题目给出一个数列，要求求出其某一区间的数字种类数。
思路：
此题我们发现要区间查询一个范围的数字种类，此时应该回忆哪些数据结构可以实现这个功能。
容易想到线段树和树状数组，当然这里个人认为用树状数组做比较简单。
最朴素的做法应该是桶排求个数，然而这道题的数据范围实在太大了，肯定会炸，这时我们需要转化一下。
转化：
题目中要求求出不重复的数字个数，那么可以理解为在这个区间内，我只需要重点关注其中一次出现这个数的位置就可以实现统计个数。
现在来思考看哪个点。
鉴于在处理时，只有端点的数值和个数已知，所以最好是看端点，这里我选择看右端点，这样我们应该从左到右地进行处理建树操作。
此时我们应该将其他的同类忽略掉。
离线：
这道题的数据范围过大，如果在线做肯定炸，因此应该离线，很简单，把数据按右端点排序（这样就可以不重不漏地从左到右处理），然后挨个处理再原序输出即可，这样的话我们只需要统一跑一遍算法，大大的降低了时间复杂度。
代码分析：
板子：
int lowbit(int x){
return x&(-x);
}
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
int get(int x){
int cnt=0;
while(x>0){
cnt+=c[x];
x-=lowbit(x);
}
return cnt;
}离线处理结构体：
const int N=1e6+5;
struct cls{
int l;
int r;
int id;
}q[N]; 分别存贮左右端点和原序。
计算答案：
int pow=1;
for(int i=1;i<=k;i++){
for(int j=pow;j<=q[i].r;j++){
if(vis[a[j]]) add(vis[a[j]],-1);
add(j,1);
vis[a[j]]=j;
}
pow=q[i].r+1;
b[q[i].id]=get(q[i].r)-get(q[i].l-1);
}这里 pow 用于存储当前待修改的第一个编号，而 vis 则是判断当前数字是否出现过，如果出现过，那么更新为新的右端点，并且将前一个位置处理的树状数组删去，完成一个区间后更新 pow。
最后原序记录，输出答案即可。