记录编号	364118	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的颜色序列	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	2.783 s
提交时间	2017-01-15 14:55:42	内存使用	142.98 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=550000;
struct Node{
	int lc,rc,sum;
}a[maxn*22];
int n,m,cnt,ans;
int pre[maxn],root[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 x,int pr,int rt,int l,int r){
	if(x>=r){
		ans+=a[rt].sum-a[pr].sum;
		return;
	}
	int mid=(l+r)>>1;
	Query(x,ls(pr),ls(rt),l,mid);
	if(x>mid)Query(x,rs(pr),rs(rt),mid+1,r);
}
void Init();
int main(){
	freopen("color_seq.in","r",stdin);freopen("color_seq.out","w",stdout);
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		root[i]=root[i-1];
		Insert(pre[x]+1,root[i],1,n);
		pre[x]=i;
	}
	for(int i=1;i<=m;i++){
		int s,t;scanf("%d%d",&s,&t);
		s=(s+ans)%n+1;t=(t+ans)%n+1;
		if(s>t)swap(s,t);
		ans=0;
		Query(s,root[s-1],root[t],1,n);
		printf("%d\n",ans);
	}
}