记录编号	175084	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.921 s
提交时间	2015-08-04 16:01:52	内存使用	7.54 MiB

#include <cstdio>
#include <algorithm>
#define lowbit(x) (x&(-x))

using namespace std;

int n,m;
int pre[1000010],ans[200010];
int a[50010];
int c[50010];

struct at{
	int y,x,i;
}ask[200010];

bool comp(at a,at b)
{
	return a.y<b.y;
}

void insert(int x,int w)
{
	while(x<=n)
	{
		c[x]+=w;
		x+=lowbit(x);
	}
	return;
}

int query(int x)
{
	int tot=0;
	while(x>0)
	{
		tot+=c[x];
		x-=lowbit(x);
	}
	return tot;
}

int main()
{
	freopen("diff.in", "r", stdin);
	freopen("diff.out", "w", stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&ask[i].x,&ask[i].y);
		ask[i].i=i;
	}
	sort(ask+1,ask+m+1,comp);
	int okask=1;
	for(int i=1;i<=n;i++)
	{
		if(!pre[a[i]])
		{
			insert(i,1);
		}
		else
		{
			insert(pre[a[i]],-1);
			insert(i,1);
		}
		pre[a[i]]=i;
		while(ask[okask].y==i)
		{
			ans[ask[okask].i]=query(ask[okask].y)-query(ask[okask].x-1);
			okask++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
}