记录编号	191992	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	4.104 s
提交时间	2015-10-09 15:25:39	内存使用	30.80 MiB

#include<cstdio>
#include<algorithm>
int n,c,m,shu;
int pre[1000010],last[1000010],o[1000010];
int ans[1000010];
struct query
{
	int l,r,id;
}ask[1000010];
inline bool comp(query a,query b)
{
	return a.r<b.r;
}
int tree[1000010];
inline void add(int x,int w)
{
	for(;x<=n;x+=x&(-x))
		tree[x]+=w;
}
inline int sum(int x)
{
	int s=0;
	while(x)
	{
		s+=tree[x];
		x-=x&(-x);
	}
	return s;
}
int main()
{
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	scanf("%d%d%d",&n,&c,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&o[i]);
		pre[i]=last[o[i]];
		last[o[i]]=i;
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&ask[i].l,&ask[i].r);
		ask[i].id=i;
	}
	std::sort(ask,ask+m,comp);
	for(int i=1;i<=n;++i)
	{
		if(pre[i])
		{
			add(pre[i]+1,-1);
			add(pre[pre[i]]+1,1);
		}
		while(i==ask[shu].r)
		{
			ans[ask[shu].id]=sum(ask[shu].l);
			++shu;
		}
	}
	for(int i=0;i<m;++i)
	    printf("%d\n",ans[i]);
}