记录编号	246866	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	3.470 s
提交时间	2016-04-07 14:14:44	内存使用	5.71 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=50010,SIZEM=200010,SIZEP=1000010;
int N,M;
int siz[SIZEP]={0};
bool vis[SIZEN]={0};
int H[SIZEN];
class miku
{
public:
	int pos;
	int L,R;
	int id;
}E[SIZEM];
int best;
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&H[i]);
	scanf("%d",&M);
	best=sqrt(N+1.0);
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&E[i].L,&E[i].R);
		E[i].pos=E[i].L/best;
		E[i].id=i;
	}
}
bool cmp(miku a,miku b)
{
	if(a.pos!=b.pos) return a.pos<b.pos;
	return a.R>b.R;
}
int now=0;
int ans[SIZEM];
void update(int x)
{
	if(vis[x])
	{
		siz[H[x]]--;
		if(!siz[H[x]]) now--;
	}
	else
	{
		if(!siz[H[x]]) now++;
		siz[H[x]]++;
	}
	vis[x]^=1;
}
void work()
{
	sort(E+1,E+M+1,cmp);
	int l=E[1].L,r=E[1].R;
	for(int i=l;i<=r;i++) update(i);
	ans[E[1].id]=now;
	for(int i=2;i<=M;i++)
	{
		while(r<E[i].R) update(++r);
		while(l<E[i].L) update(l++);
		while(r>E[i].R) update(r--);
		while(l>E[i].L) update(--l);
		ans[E[i].id]=now;
	}
	for(int i=1;i<=M;i++) printf("%d\n",ans[i]);
}
int main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	read();
	work();
	return 0;
}