记录编号	434082	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	1.169 s
提交时间	2017-08-07 06:40:06	内存使用	3.27 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
int n,m,ans[200005],hh[50005],a[50005],cnt,h,kuai[50005];
map<int,int> mp;
struct Q
{
	int l,r,id;
} q[200005];
bool cmp(Q a,Q b)
{
	return (kuai[a.l]==kuai[b.l])? (a.r<b.r):(kuai[a.l]<kuai[b.l]);
}
int yjn()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%d",&n);h=sqrt(n);if(h>50)h=50;
	int x;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(!mp.count(x))
		   mp[x]=++cnt;
		a[i]=mp[x];
		kuai[i]=(i-1)/h+1;
	}
	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+m+1,cmp);
	int an=0,l=0,r=l;
	for(int i=1;i<=m;i++)
	{
		for(;l<q[i].l;l++){hh[a[l]]--;if(!hh[a[l]])an--;}
		for(;l>q[i].l;l--){hh[a[l-1]]++;if(hh[a[l-1]]==1)an++;}
		for(;r<q[i].r;r++){hh[a[r+1]]++;if(hh[a[r+1]]==1)an++;}
		for(;r>q[i].r;r--){hh[a[r]]--;if(!hh[a[r]])an--;}
		ans[q[i].id]=an;
		//cout<<an<<endl;system("pause");
	}
	for(int i=1;i<=m;i++)
	   printf("%d\n",ans[i]);
}
int qty=yjn();
int main(){;}