记录编号	255544	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的颜色序列	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.421 s
提交时间	2016-04-28 06:25:57	内存使用	106.69 MiB

#define maxn 500010ul
#define maxt 10000010ul

#include <stdio.h>
#include <algorithm>

int n,m,tot,L[maxt],R[maxt],tr[maxt],root[maxn],pre[maxn];

void read(int &x){
	x=0;int c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return;
}

void ins(int ls,int &rt,int l,int r,int x){
	rt=++tot,L[rt]=L[ls],R[rt]=R[ls],tr[rt]=tr[ls]+1;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) ins(L[ls],L[rt],l,mid,x);
	else ins(R[ls],R[rt],mid+1,r,x);
	return;
}

int query(int ls,int rt,int l,int r,int x){
	if(tr[rt]==tr[ls]) return 0;
	if(r<=x) return tr[rt]-tr[ls];
	int mid=(l+r)>>1,ret=query(L[ls],L[rt],l,mid,x);
	if(x>mid) ret+=query(R[ls],R[rt],mid+1,r,x);
	return ret;
}

int main(){
	freopen("color_seq.in","r",stdin);
	freopen("color_seq.out","w",stdout);
	read(n),read(m);
	for(int i=1,x;i<=n;i++)
		read(x),ins(root[i-1],root[i],0,n,pre[x]),pre[x]=i;
	for(int i=1,x,y,last=0;i<=m;i++){
		read(x),read(y),x=(x+last)%n+1,y=(y+last)%n+1;
		if(x>y) std::swap(x,y);
		printf("%d\n",last=query(root[x-1],root[y],0,n,x-1));
	}
	return 0;
}