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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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);
	scanf("%d%*d%d",&n,&m);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&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--){
		scanf("%d%d",&s,&t);
		s^=ans;t^=ans;
		ans=0;
		query(1,n,root[t],root[s-1]);
		printf("%d\n",ans);
	}
	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]);
}