记录编号	343314	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的颜色序列	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	2.149 s
提交时间	2016-11-09 07:53:59	内存使用	83.16 MiB

#define pro __attribute__((optimize("O3")))
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
 
using namespace std;
#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
char cha[10000000],*ptr=cha;
char chout[9000000],*pout=chout;
#define getchar() (*ptr++)
 
pro inline void read(int &x) {
	 bool flag = 0;register char c;
	 while((c=getchar())>'9'||c<'0')
	   if(c == '-') flag = 1;
	 x = c-'0';
	 while((c=getchar())<='9'&&c>='0')
	  x = ((x<<1)+(x<<3))+c-'0';
	 if(flag) x = -x;  
}
pro inline void out(int x) {
    if(!x)*pout++='0';
    int p=0;char buf[10];
    while(x) buf[++p]=x%10+'0',x/=10;
    while(p) *pout++=buf[p--];
    *pout++='\n';
}
 
#define Rep(i, x, y) for (register int i = (x), _ = (y); i <= _; i++)
typedef long long lg;
#define MAXX 500001
 
struct TREE {int l,r,sum;}t[MAXX*20];
int root[MAXX],cnt = 1;
int next[MAXX],pre[MAXX];
int n,m;
 
pro void build(int num,int &o,int l,int r) {
    t[++cnt] = t[o];
    o = cnt; t[o].sum++;
	if(l == r) return;
	int mid = (l+r)>>1;
	if(num <= mid) build(num,t[o].l,l,mid);
	else build(num,t[o].r,mid+1,r);
}
 
pro int query(int lt,int rt,int num,int l,int r) {
	if(l == r) return t[rt].sum - t[lt].sum;	
	int mid = (r+l)>>1;
	if(num <= mid) return query(t[lt].l,t[rt].l,num,l,mid) + (t[t[rt].r].sum - t[t[lt].r].sum);
	return query(t[lt].r,t[rt].r,num,mid+1,r);
}
 
pro int work() {
    FRE(color_seq);
	fread(ptr,1,10000000,stdin);
    read(n);read(m);int x;
	Rep(i,1,n) {
	   read(x);
	   if(pre[x]) next[pre[x]] = i;
	   pre[x] = i;
	}
	Rep(i,1,n) {
	  if(!next[i]) next[i] = n+1;
	  root[i] = root[i-1];
	  build(next[i],root[i],1,n+1);
    }
	register int r,l,ans = 0;
	Rep(i,1,m) {
	  read(l),read(r);
	  l = (l+ans)%n+1;
	  r = (r+ans)%n+1;
	  if(l > r) {register int c = r;r = l;l = c;}
	  out(ans = query(root[l-1],root[r],r+1,1,n+1));
    }
	fwrite(chout,1,pout-chout,stdout);
}
 
int nott = work();
 
int main(){;}