记录编号	332005	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	coolkid	是否通过	通过
代码语言	C++	运行时间	1.854 s
提交时间	2016-10-28 11:42:54	内存使用	20.15 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=200010;
const int MAXC=2000010;
struct Query{
	int L,R,id;
	bool operator < (const Query &q)const{
		return R<q.R;
	}
	void work(){
		L++;R++;
	}
}qu[MAXN];
int A[MAXN];
int pre[MAXN];
int last[MAXC];
int n,m;
int C[MAXC];
int ans[MAXN];

void init(){
	memset(pre,0,sizeof(pre));
	memset(last,0,sizeof(last));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]),A[i]+=1000000;
		pre[i]=last[A[i]];
		last[A[i]]=i;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&qu[i].L,&qu[i].R),qu[i].id=i;
	sort(qu+1,qu+1+m);
//	for(int i=1;i<=m;i++) qu[i].work();
	memset(C,0,sizeof(C));
}

inline int lowbit(int x){
	return x&(-x);
}

void Add(int x,int p){
	while(p<MAXC){
		C[p]+=x;
		p+=lowbit(p);
	}
}

int Qu(int p){
//	printf(">>>%d\n",p);
	int res=0;
	while(p){
		res+=C[p];
		p-=lowbit(p);
	}
	return res;
}

void work(){
	int Len=1;
	for(int i=1;i<=n;i++){
		Add(1,i);
		if(pre[i]) Add(-1,pre[i]);
		while(qu[Len].R==i&&Len<=m){
			ans[qu[Len].id]=Qu(qu[Len].R)-Qu(qu[Len].L-1);
			Len++;
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	init();
	work();
	#ifdef DEBUG
//		while(1);
	#endif
}
/*
9 2
2 5 4 1 2 3 6 2 4
0 8
2 6

6
1 2 3 4 3 5
3
1 2
3 5
2 6
*/