记录编号	175155	评测结果	AAATTTTTTA
题目名称	[SDOI 2009] HH的项链	最终得分	40
用户昵称	Aglove	是否通过	未通过
代码语言	C++	运行时间	6.642 s
提交时间	2015-08-04 18:54:39	内存使用	4.89 MiB

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=50010,Maxn=1000010;
int n,blo,m,k,u,v;
int a[maxn],b[maxn],p[maxn],next[maxn],h[Maxn];
void qread(int &num){
	num=0;char ch=getchar();
	while(ch<'!')ch=getchar();
	while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
}
void pre(int x){
	int l=(x-1)*blo+1,r=min(n,x*blo);
	sort(b+l,b+r+1);
}
int doublekill(int x,int v){
	int l=(x-1)*blo+1,r=min(n,x*blo),q=l;
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]<v)l=mid+1;
		else r=mid-1;
	}return l-q;
}
int main(){
	freopen("diff.in","r",stdin);freopen("diff.out","w",stdout);
	qread(n);blo=(int)(sqrt(n));
	for(int i=1;i<=n;++i){
		qread(a[i]);
		p[i]=(i-1)/blo+1;
		next[i]=h[a[i]];
		h[a[i]]=i;b[i]=next[i];
	}
	int k=n/blo+1;if(n%blo==0)--k;
	for(int i=1;i<=k;++i)pre(i);
	qread(m);
	for(int i=1;i<=m;++i){
		qread(u);qread(v);
		int ans=0;
		if(p[u]==p[v]){
			for(int i=u;i<=v;++i)if(next[i]<u)ans++;
		}else{
			for(int i=u;i<=p[u]*blo;++i)if(next[i]<u)ans++;
			for(int i=(p[v]-1)*blo+1;i<=v;++i)if(next[i]<u)ans++;
			for(int i=p[u]+1;i<p[v];++i)ans+=doublekill(i,u);
		}
		printf("%d\n",ans);
	}return 0;
}