记录编号	191990	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	1.328 s
提交时间	2015-10-09 15:24:09	内存使用	30.81 MiB

#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
struct dd{
   int l,r,id;
}jie[1000009];
inline int in() {
	int ret,neg;	char ch;
	ret = neg = 0 ; while (!isdigit(ch=getchar())&&ch!='-') ;
	if (ch=='-') neg = 1 , ch=getchar() ;
	while (ret = ret*10+ch-'0' , isdigit(ch=getchar())) ;
	if (neg) ret = -ret ;
	return ret ;
}
int belong[1000006],s[1000006],color[1000005],ans,n,m,c;
int as[1000006],bs[1000006];
bool comp(const dd & a,const dd & b){
	if(belong[a.l]==belong[b.l]) return a.r<b.r;
	return a.l<b.l;
}
void update(int x,int rt){
   s[color[x]]+=rt;
   if((s[color[x]]==1&&rt>0)||(s[color[x]]==0&&rt<0))
      ans+=rt;
}
int main(){
	freopen("diff.in", "r", stdin);
	freopen("diff.out", "w", stdout);
	n=in();
	int bol=(int)sqrt(n+0.5);
	for(int i=1;i<=n;++i) color[i]=in();
	for(int i=1;i<=n;++i) belong[i]=(int)((i-1)/bol)+1;
	m=in();
	for(int i=1;i<=m;++i){
	   jie[i].l=in();jie[i].r=in();jie[i].id=i;
	}
	sort(jie+1,jie+m+1,comp);
	int le=jie[1].l,re=jie[1].r;
	for(int i=le;i<=re;++i) update(i,1);
	if(le==re) as[jie[1].id]=0;
	else as[jie[1].id]=ans;
	for(int i=2;i<=m;++i){
	  while(re<jie[i].r) update(++re,1);
	  while(re>jie[i].r) update(re--,-1);
	  while(le>jie[i].l) update(--le,1);
	  while(le<jie[i].l) update(le++,-1);
	  if(jie[i].r==jie[i].l) as[jie[i].id]=0;
	  else as[jie[i].id]=ans;
	}
	for(int i=1;i<=m;++i) printf("%d\n",as[i]);
	return 0;
}