记录编号	142085	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	4.638 s
提交时间	2014-12-06 10:40:34	内存使用	7.94 MiB

#include<bits/stdc++.h>
using namespace std;
struct s
{
	int l,n,r;
}q[200010];
int a[50010],b[200010],i,j,l[1000010],m,n,p[50010];
struct f
{
	int a[50010],c[50010];
	void o(int i,int x)
	{
		a[i]+=x;
		while(i<=n)
		{
			c[i]+=x;
			i+=(i&-i);
		}
	}
	int u(int i)
	{
		int r=0;
		while(i)
		{
			r+=c[i];
			i-=(i&-i);
		}
		return r;
	}
}t;
int d(const void *a,const void *b)
{
	return(*(s*)a).r-(*(s*)b).r;
}
main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=l[a[i]];
		l[a[i]]=i;
	}
	cin>>m;
	for(i=1;i<=m;i++)
	{
		q[i].n=i;
		cin>>q[i].l>>q[i].r;
	}
	qsort(q+1,m,sizeof(s),d);
	for(i=1;i<=m;i++)
	{
		while(j<q[i].r)
		{
			j++;
			t.o(j+1,-1);
			t.o(p[j]+1,1);
		}
		b[q[i].n]=t.u(q[i].l);
	}
	for(i=1;i<=m;i++)
		cout<<b[i]<<endl;
}