题意概括：

题目给出一个数列，要求求出其某一区间的数字种类数。

思路：

此题我们发现要区间查询一个范围的数字种类，此时应该回忆哪些数据结构可以实现这个功能。

容易想到线段树和树状数组，当然这里个人认为用树状数组做比较简单。

最朴素的做法应该是桶排求个数，然而这道题的数据范围实在太大了，肯定会炸，这时我们需要转化一下。

转化：

题目中要求求出不重复的数字个数，那么可以理解为在这个区间内，我只需要重点关注其中一次出现这个数的位置就可以实现统计个数。

现在来思考看哪个点。

鉴于在处理时，只有端点的数值和个数已知，所以最好是看端点，这里我选择看右端点，这样我们应该从左到右地进行处理建树操作。

此时我们应该将其他的同类忽略掉。

离线：

这道题的数据范围过大，如果在线做肯定炸，因此应该离线，很简单，把数据按右端点排序（这样就可以不重不漏地从左到右处理），然后挨个处理再原序输出即可，这样的话我们只需要统一跑一遍算法，大大的降低了时间复杂度。

代码分析：

板子：

CPP

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;
}

离线处理结构体：

CPP

const int N=1e6+5;
struct cls{
	int l;
	int r;
	int id;
}q[N];

分别存贮左右端点和原序。

计算答案：

CPP

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。

最后原序记录，输出答案即可。

P1972 [SDOI2009] HH的项链

文章操作