记录编号	351779	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	3.259 s
提交时间	2016-11-16 19:03:16	内存使用	27.72 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=1000010;
namespace mine{
//#define NEGATE_NEEDED
	template<class T>inline void readint(T &__x){
		static int __c;
#ifdef NEGATE_NEEDED
		static bool __neg;
#endif
		__x=0;
#ifdef NEGATE_NEEDED
		__neg=false;
#endif
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
#ifdef NEGATE_NEEDED
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
#endif
		for(;__c>='0'&&__c<='9';__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48);
#ifdef NEGATE_NEEDED
		if(__neg)__x=-__x;
#endif
	}
	template<class T>inline void writeint(T __x){
		static int __a[25],__i,__j;
#ifdef NEGATE_NEEDED
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
#endif
		__i=0;
		do{
			__a[__i++]=__x%10^48;
			__x/=10;
		}while(__x);
#ifdef NEGATE_NEEDED
		if(__neg)putchar('-');
#endif
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
struct Q{
	int l,r,id;
	bool operator<(const Q &q)const{return r<q.r;}
}q[maxn];
void add(int,int);
int query(int);
int n,m,a[maxn],p[maxn],last[maxn]={0},ans[maxn],c[maxn]={0},cnt=1;
int main(){
#define MINE
#ifdef MINE
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
#endif
	readint(n);readint(m);readint(m);
	for(int i=1;i<=n;i++)readint(a[i]);
	for(int i=1;i<=m;i++){
		readint(q[i].l);readint(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=n;i++){
		p[i]=last[a[i]];
		last[a[i]]=i;
		if(p[i]){
			add(p[p[i]]+1,1);
			add(p[i]+1,-1);
		}
		while(cnt<=m&&q[cnt].r==i){
			ans[q[cnt].id]=query(q[cnt].l);
			cnt++;
		}
	}
	for(int i=1;i<=m;i++){
		writeint(ans[i]);
		putchar('\n');
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
inline void add(int x,int d){
	while(x<=n){
		c[x]+=d;
		x+=lowbit(x);
	}
}
inline int query(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}