记录编号	255802	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的颜色序列	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	2.895 s
提交时间	2016-04-28 19:37:24	内存使用	294.05 MiB

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int tot=1,n,m,la[maxn];
int T[maxn*19],lson[maxn*19],rson[maxn*19],c[maxn*19];

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int update(int root,int pos){
    if (!root) root=tot++,c[root]=0;
    int nr=tot++,tmp=nr,l=0,r=m;
    c[nr]=c[root]+1;
    while (l<r){
        int mid=(l+r)>>1;
        if (pos<=mid){
            lson[nr]=tot++;rson[nr]=rson[root];
            r=mid;root=lson[root];nr=lson[nr];
        }else if (pos>mid){
            lson[nr]=lson[root];rson[nr]=tot++;
            l=mid+1;root=rson[root];nr=rson[nr];
        }c[nr]=c[root]+1;
    }return tmp;
}

int query(int lr,int rr,int l,int r,int L,int R){
	if (c[rr]-c[lr]==0) return 0;
    if (l==L&&R==r) return c[rr]-c[lr];
    int mid=(l+r)>>1;
    if (R<=mid) return query(lson[lr],lson[rr],l,mid,L,R);
    else if (L>mid) return query(rson[lr],rson[rr],mid+1,r,L,R);
    else return query(lson[lr],lson[rr],l,mid,L,mid)+
                query(rson[lr],rson[rr],mid+1,r,mid+1,R);
}

int main(){
	freopen("color_seq.in","r",stdin);
	freopen("color_seq.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i){
		int x; x=read();
		T[i]=update(T[i-1],la[x]);
		la[x]=i;
	}
	int lastans=0;
	for (int i=1;i<=m;++i){
		int x,y; x=read(); y=read();
		x=(x+lastans)%n+1;
		y=(y+lastans)%n+1;
		if (x>y) swap(x,y);
		lastans=query(T[x-1],T[y],0,n,0,x-1);
		printf("%d\n",lastans);
	}
	//while (1);
}