记录编号	192160	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.971 s
提交时间	2015-10-09 21:13:30	内存使用	27.02 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=1000000+10;
int Ans[maxn];
struct A{
	int l,r,id;
	int block;
	bool operator < (const A &a) const{
		if (block==a.block) return r<a.r;
		return block<a.block;
	}
	void read(int i){
		scanf("%d%d",&l,&r);
		id=i;
	}
}ask[maxn];
int cnt[maxn],a[maxn],n,m,blo;

int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	scanf("%d",&n); blo=sqrt(n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;++i){
		ask[i].read(i);
		ask[i].block=(ask[i].l-1)/blo+1;
	}
	sort(ask+1,ask+m+1);
	cnt[a[1]]++;
	for (int i=1,l=1,r=1,ans=1;i<=m;++i){
		while (r>ask[i].r){
			cnt[a[r]]--;
			if (!cnt[a[r]]) ans--;
			r--;
		}
		while (r<ask[i].r){
			r++;
			cnt[a[r]]++;
			if (cnt[a[r]]==1) ans++;
		}
		while (l>ask[i].l){
			l--;
			cnt[a[l]]++;
			if (cnt[a[l]]==1) ans++;
		}
		while (l<ask[i].l){
			cnt[a[l]]--;
			if (cnt[a[l]]==0) ans--;
			l++;
		}
		Ans[ask[i].id]=ans;
	}
	for (int i=1;i<=m;++i) printf("%d\n",Ans[i]);
	return 0;
}