记录编号	364124	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]采花	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	3.967 s
提交时间	2017-01-15 15:22:19	内存使用	130.01 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ls(x) (a[x].lc)
#define rs(x) (a[x].rc)
const int maxn=250000;
struct Node{
	int lc,rc,sum;
}a[maxn*44];
int n,m,ans=0,cnt;
struct Chairman_Tree{
	int root[maxn],pre[maxn];
	void Insert(int x,int & rt,int l,int r){
		a[++cnt]=a[rt];rt=cnt;
		a[rt].sum++;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(x<=mid)Insert(x,ls(rt),l,mid);
		else Insert(x,rs(rt),mid+1,r);
	}
	void Query(int s,int t,int pr,int rt,int l,int r,int type){
		if(s<=l && t>=r){
			ans+=type*(a[rt].sum-a[pr].sum);
			return;
		}
		int mid=(l+r)>>1;
		if(s<=mid)Query(s,t,ls(pr),ls(rt),l,mid,type);
		if(t>mid)Query(s,t,rs(pr),rs(rt),mid+1,r,type);
	}
}now,last;
void Init();
int main(){
	freopen("flower++.in","r",stdin);freopen("flower++.out","w",stdout);
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%*d%d",&n,&m);
	int haha=0;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		now.root[i]=now.root[i-1];
		last.root[i]=last.root[i-1];

		now.Insert(now.pre[x]+1,now.root[i],1,n);
		last.Insert(last.pre[x]+1,last.root[i],1,n);
		
		last.pre[x]=now.pre[x];
		now.pre[x]=i;
	}
	for(int i=1;i<=m;i++){
		int s,t;scanf("%d%d",&s,&t);
		s^=ans;t^=ans;ans=0;
		now.Query(s+1,t,now.root[s-1],now.root[t],1,n,1);
		last.Query(s+1,t-1,last.root[s-1],last.root[t],1,n,-1);
		printf("%d\n",ans);
	}
}