记录编号	550970	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	19.849 s
提交时间	2020-03-27 00:51:51	内存使用	32.29 MiB

//只是把一般的莫队加入答案条件由出现一次以上变成了出现两次以上 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm> 
#define R register
using namespace std;
struct PE
{
	int l,r,id;
};
PE Q[1000001];
int pos[1000001],col[1000001],cnt[1000001],ans[1000001];
int nl,nr,sum,n,m,c,block;
void read(int &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		//真就2倍+8倍=10倍呗 
		ch=getchar();
	} 
	x*=f;
}
bool Function(PE x,PE y)
{
	if(pos[x.l]==pos[y.l])
	{
		return x.r<y.r;
	}
	return x.l<y.l;
}
int LINYIN()
{
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	read(n);
	read(c);
	read(m);
	block=sqrt(n);
	for(R int i=1;i<=n;i++)
	{
		read(col[i]);
		pos[i]=i/block+1;
	}
	for(R int i=1;i<=m;i++)
	{
		read(Q[i].l);
		read(Q[i].r);
		Q[i].id=i;
	}
	sort(Q+1,Q+1+m,Function);
	nl=1,nr=0,sum=0;
	for(R int i=1;i<=m;i++)
	{
		while(nl<Q[i].l)
		{
			if(--cnt[col[nl++]]==1)
				--sum;
			//DELETE(nl++);
		}
		while(nl>Q[i].l)
		{
			if(++cnt[col[--nl]]==2)
				++sum;
			//ADD(--nl);
		}
		while(nr<Q[i].r)
		{
			if(++cnt[col[++nr]]==2)
				++sum;
			//ADD(++nr);
		}
		while(nr>Q[i].r)
		{
			if(--cnt[col[nr--]]==1)
				--sum;
			//DELETE(nr--);
		}
		ans[Q[i].id]=sum;
	}
	for(R int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}
int SED=LINYIN();
int main()
{
	;
}