记录编号	295902	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.140 s
提交时间	2016-08-14 17:55:24	内存使用	11.16 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50010,M=200010;
int n,m,a[N],b[M],l,now;
int cnt[1000010],head,tail,level;
int color[1000010];
struct qj{
	int l,r,ans;
}q[M];
bool cmp(const int x,const int y){
	int a1=q[x].l/l,a2=q[y].l/l;
	return a1!=a2?a1<a2:q[x].r<q[y].r;
}
inline void push(int x){
	if (color[x]!=level) color[x]=level,cnt[x]=0;
	if (!cnt[x]) now++;cnt[x]++;
}
inline void del(int x){
	cnt[x]--;if (!cnt[x]) now--;
}
int main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%d",&n);l=sqrt(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),b[i]=i;
	sort(b+1,b+m+1,cmp);
	for (int i=1;i<=m;){
		head=tail=q[b[i]].l;now=0;level=q[b[i]].l/l;
		push(a[head]);
		while (tail<q[b[i]].r) tail++,push(a[tail]);
		while (q[b[i]].l/l==level){
			while (tail<q[b[i]].r) tail++,push(a[tail]);
			while (head>q[b[i]].l) head--,push(a[head]);
			while (head<q[b[i]].l) del(a[head]),head++;
			q[b[i]].ans=now;i++;
		}
	}
	for (int i=1;i<=m;i++) printf("%d\n",q[i].ans);
	return 0;
}