记录编号	405227	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]采花	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.731 s
提交时间	2017-05-16 11:27:05	内存使用	96.14 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int _size_=(1<<20)+1;
char is[_size_],*pi=is,*ie=is+_size_,os[_size_],*po=os,*oe=os+_size_;
template<class T>inline void readint(T &t){
	int x=0;
	while(*pi<48)if(++pi==ie)fread(pi=is,sizeof(is),sizeof(char),stdin);
	while(*pi>47){
		x=x*10+(*pi^48);
		if(++pi==ie)fread(pi=is,sizeof(is),sizeof(char),stdin);
	}
	t=x;
}
template<class T>inline void writeint(T x){
	static int a[25];
	if(!x){
		*po='0';
		if(++po==oe)fwrite(po=os,sizeof(os),sizeof(char),stdout);
	}
	else{
		int i=0;
		while(x){
			a[++i]=x%10;
			x/=10;
		}
		while(i){
			*po=a[i]^48;
			i--;
			if(++po==oe)fwrite(po=os,sizeof(os),sizeof(char),stdout);
		}
	}
	*po='\n';
	if(++po==oe)fwrite(po=os,sizeof(os),sizeof(char),stdout);
}
const int maxn=200010,maxm=maxn*40;
void build(int,int,int&);
void query(int,int,int,int);
int sm[maxm],lc[maxm],rc[maxm],root[maxn],cnt=0;
int n,m,last[maxn],p[maxn],s,t,d,ans=0;
int main(){
	freopen("flower++.in","r",stdin);
	freopen("flower++.out","w",stdout);
	readint(n);
	readint(m);
	readint(m);
	for(int i=1,x;i<=n;i++){
		readint(x);
		t=p[i]=last[x];
		root[i]=root[i-1];
		if(t){
			d=1;
			build(1,n,root[i]);
				t=p[t];
			if(t){
				d=-1;
				build(1,n,root[i]);
			}
		}
		last[x]=i;
	}
	while(m--){
		readint(s);
		readint(t);
		s^=ans;t^=ans;
		ans=0;
		query(1,n,root[t],root[s-1]);
		writeint(ans);
	}
	fwrite(os,po-os,sizeof(char),stdout);
	return 0;
}
void build(int l,int r,int &rt){
	int x=++cnt;
	sm[x]=sm[rt]+d;
	lc[x]=lc[rt];
	rc[x]=rc[rt];
	rt=x;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(t<=mid)build(l,mid,lc[rt]);
	else build(mid+1,r,rc[rt]);
}
void query(int l,int r,int rt,int pr){
	if(!rt&&!pr)return;
	if(s<=l&&t>=r){
		ans+=sm[rt]-sm[pr];
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(l,mid,lc[rt],lc[pr]);
	if(t>mid)query(mid+1,r,rc[rt],rc[pr]);
}