记录编号	600119	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	0.809 s
提交时间	2025-04-15 22:16:08	内存使用	9.03 MiB

#include<bits/stdc++.h>
using namespace std;
inline int re()
{
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=1000010;
int n,m,lr,sum;
int a[N],last[N],ans[N],c[N];
struct q
{
	int l,r,bi;
}qs[N];
bool cmp(q x,q y){return x.r<y.r;}
void add(int w,int z)
{
	while(w<=N-10)
	{
		c[w]+=z;
		w+=w&-w;
	}
}
int query(int w)
{
	sum=0;
	while(w)
	{
		sum+=c[w];
		w-=w&-w;
	}
	return sum;
}
int main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	n=re();
	for(int i=1;i<=n;i++) a[i]=re();
	m=re();
	for(int i=1;i<=m;i++) qs[i].l=re(),qs[i].r=re(),qs[i].bi=i;
	sort(qs+1,qs+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		while(lr<qs[i].r)
		{
			lr++;
			if(last[a[lr]]) add(last[a[lr]],-1);
			last[a[lr]]=lr;add(lr,1);
		}
		ans[qs[i].bi]=query(qs[i].r)-query(qs[i].l-1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}