记录编号	306403	评测结果	AAAAAAAAAA
题目名称	421.[SDOI 2009] HH的项链	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	3.072 s
提交时间	2016-09-11 22:31:34	内存使用	10.07 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=50010,M=200010,K=1000010;
int num[K],hsh[K],a[N],n,Q,block,cnt;
int ql[M],qr[M],p[M],ans[M],tmp,tim;
bool cmp(int x,int y){
	return (ql[x]-1)/block!=(ql[y]-1)/block?ql[x]<ql[y]:qr[x]<qr[y];
}
void Add(int x){
	if(!num[x])tmp++;
	num[x]++;
}
void Min(int x){
	if(num[x]==1)tmp--;
	num[x]--;
}
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		if(!hsh[x])hsh[x]=++cnt;
		a[i]=hsh[x];
	}
	cin>>Q;
	for(int i=1;i<=Q;i++)	
		cin>>ql[i]>>qr[i],p[i]=i;
	block=(int)sqrt(n+0.5);
	sort(p+1,p+Q+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=Q;i++){
		while(ql[p[i]]<l)Add(a[--l]);
		while(ql[p[i]]>l)Min(a[l++]);
		while(qr[p[i]]>r)Add(a[++r]);
		while(qr[p[i]]<r)Min(a[r--]);			
		ans[p[i]]=tmp;
	}
	for(int i=1;i<=Q;i++)
		cout<<ans[i]<<"\n";	
	return 0;
}