记录编号	600113	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	1.434 s
提交时间	2025-04-15 21:41:42	内存使用	8.97 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int M=50010;
struct poi{
	int l,r,id;
}q[N];
int n,m,ans,len,a[M],f[N],vis[N*5];
bool cmp(poi x,poi y){
	if(x.l/len!=y.l/len)return x.l<y.l;
	else return x.r<y.r;
}
void add(int x){
	vis[a[x]]++;
	if(vis[a[x]]==1)ans++;
}
void re(int x){
	vis[a[x]]--;
	if(!vis[a[x]])ans--;
}
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%d",&n);
	len=sqrt(double(n));
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int L=0,R=0;ans=0;
	for(int i=1;i<=m;i++){
		while(L<q[i].l)re(L),L++;
		while(L>q[i].l)L--,add(L);
		while(R<q[i].r)R++,add(R);
		while(R>q[i].r)re(R),R--;
		f[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)printf("%d\n",f[i]);
	return 0;
}