记录编号	449537	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	2.647 s
提交时间	2017-09-14 16:40:50	内存使用	11.24 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int n,m,blo;
int w[50005],cnt[1000005],bl[1000005];
int bloans[5005],l[5005],r[5005];
int ans[200005];
struct que{
	int l,r,id;
}q[200005];
bool operator<(que a,que b){
	if(bl[a.l]!=bl[b.l])
		return a.l<b.l;
	return a.r<b.r;
}
int mx;
inline void del(int x){
	--cnt[x];
	if(cnt[x]==0)
		--bloans[bl[x]];
}
inline void add(int x){
	++cnt[x];
	if(cnt[x]==1)
		++bloans[bl[x]];
}
int tot;
inline int query(){
	int ret(0);
	for(int i=1;i<=tot;++i)
		ret+=bloans[i];
	return ret;
}
inline int gg(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)
		w[i]=read(),mx=max(mx,w[i]);
	blo=sqrt(mx>>1);
	for(int i=1;i<=mx;++i){
		bl[i]=(i-1)/blo+1;
		r[bl[i]]=i;
		tot=bl[i];
		if(!l[bl[i]])
			l[bl[i]]=i;
	}
	m=read();
	for(int i=1;i<=m;++i)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1);
	int l(1),r(0);
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(w[l]);
			++l;
		}
		while(r>q[i].r){
			del(w[r]);
			--r;
		}
		while(l>q[i].l){
			--l;
			add(w[l]);
		}
		while(r<q[i].r){
			++r;
			add(w[r]);
		}
		ans[q[i].id]=query();
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	return 0;
}
int K(gg());
int main(){;}