记录编号	302895	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	1.389 s
提交时间	2016-09-04 18:06:04	内存使用	76.58 MiB

#include<cstdio>
#include<algorithm>
#define maxn 2000000
#define u tree[x]
#define lc tree[x<<1]
#define rc tree[x<<1|1]
using namespace std;
class poi{
public:
	int l,r,sum;
	poi(){sum=0;}
}tree[maxn],q[maxn];
int to[maxn]={0},next[maxn]={0},s[maxn]={0},n,m;
void maketree(int x,int l,int r){
	u.l=l,u.r=r,u.sum=0;
	if (l==r){	
	}
	else{
		maketree(x<<1,l,(l+r>>1));
		maketree(x<<1|1,(l+r>>1)+1,r);
	}
}
void add(int x,int l,int r,int t){
	if (l<=u.l&&u.r<=r){
		u.sum+=t;
	}
	else{
		if (l<=lc.r){
			add(x<<1,l,r,t);
		}
		if (r>=rc.l){
			add(x<<1|1,l,r,t);
		}
		u.sum=lc.sum+rc.sum;
	}
}
int sum(int x,int l,int r){
	if (l<=u.l&&u.r<=r){
		return u.sum;
	}
	else{
		int t=0;
		if (l<=lc.r){
			t+=sum(x<<1,l,r);
		}
		if (r>=rc.l){
			t+=sum(x<<1|1,l,r);
		}
		return t;
	}
}
bool cmp(poi a,poi b){
	return a.l<b.l;
}
int t=1,ans[maxn]={0};
void answer(int x){
	while (q[t].l==x){
		ans[q[t].sum]=sum(1,q[t].l,q[t].r);
		t++;
	}
}
inline void work(){
	scanf("%d",&n);
	maketree(1,1,n);
	for (int i=1;i<=n;i++){
		scanf("%d",&s[i]);
	}
	for (int i=1;i<=n;i++){
		if (to[s[i]]==0) add(1,i,i,1);
		next[to[s[i]]]=i;
		to[s[i]]=i;
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].sum=i;
	}
	sort(q+1,q+m+1,cmp);
	for (int i=1;i<=n;i++){
		answer(i);
		add(1,next[i],next[i],1);
	}
	for (int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
}

int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	work();
	return 0;
}