记录编号	483311	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	20.477 s
提交时间	2018-01-16 10:51:31	内存使用	30.92 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
struct poi{int l,r,id;}q[maxn];
int n,c,m,ans,a[maxn],vis[maxn],Ans[maxn],Block;
bool cmp(poi x,poi y){
	if(x.l/Block!=y.l/Block)return x.l<y.l;
	else return x.r<y.r;
}
int main(){
	freopen("1flower.in","r",stdin);
	freopen("1flower.out","w",stdout);
	scanf("%d%d%d",&n,&c,&m);Block=sqrt(double(n));
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int L=0,R=0;
	for(int i=1;i<=m;i++){
		while(L<q[i].l){
			vis[a[L]]--;
			if(vis[a[L]]==1)ans--;
			L++;
		}
		while(L>q[i].l){
			L--,vis[a[L]]++;
			if(vis[a[L]]==2)ans++;
		}
		while(R<q[i].r){
			R++,vis[a[R]]++;
			if(vis[a[R]]==2)ans++;
		}
		while(R>q[i].r){
			vis[a[R]]--;
			if(vis[a[R]]==1)ans--;
			R--;
		}
		Ans[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)printf("%d ",Ans[i]);
	return 0;
}