记录编号	313192	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]easy seq	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	13.764 s
提交时间	2016-09-28 18:44:14	内存使用	415.31 MiB

#include <cstdio>
const int N=100001,M=301,B=334;
int n,Q,lmn[N][M],rmx[N][M];
int dp[M][M],a[N],bel[N];
int fst[N][M],lst[N][M];
int st[M],ed[M],tot;
int h[N],vis[N],tim;
char c;int x;
__inline int min(int x,int y){return x>y?y:x;}
__inline int max(int x,int y){return x<y?y:x;}
__inline int Read(){
	while(x=getchar()-48,x>9||x<0);
	while(c=getchar()-48,c<=9&&c>=0)x=x*10+c;
	return x;
}
int main(){
	freopen("easy_seq.in","r",stdin);
	freopen("easy_seq.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(register int i=1;i<=n;i++)a[i]=Read();
	for(register int i=1;i<=n;i++)bel[i]=(i-1)/B+1;
	for(register int i=1;i<=n;i++)ed[bel[i]]=i;
	for(register int i=n;i>=1;i--)st[bel[i]]=i;
	
	tot=bel[n];
	
	for(register int i=n;i>=1;i--)fst[a[i]][bel[i]]=i;
	for(register int i=1;i<=n;i++)lst[a[i]][bel[i]]=i;
	
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=bel[i];j++)
			lmn[i][j]=fst[a[i]][j];
		for(register int j=bel[i];j<=tot;j++)
			rmx[i][j]=lst[a[i]][j];
	}
	
	for(register int i=1;i<=n;i++){
		for(register int j=bel[i]-1;j>=1;j--)
			if(!lmn[i][j])lmn[i][j]=lmn[i][j+1];
			else lmn[i][j]=min(lmn[i][j],lmn[i][j+1]); 
		for(register int j=bel[i]+1;j<=tot;j++)
			rmx[i][j]=max(rmx[i][j],rmx[i][j-1]);
	}
	
	for(register int j=1,i;j<=n;j++){i=bel[j];
		dp[i][i]=max(dp[i][i],lst[a[j]][i]-j);
		dp[i][i]=max(dp[i][i],j-fst[a[j]][i]);
	}
	
	for(register int k=2;k<=tot;k++)
		for(register int i=1,j;(j=i+k-1)<=tot;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
			for(register int t=st[i];t<=ed[i];t++)
			dp[i][j]=max(dp[i][j],rmx[t][j]-t);
		}	
	int l_,r_,l,r,ans=0;
	while(Q--){
		l=Read();r=Read();
		l_=min((l+ans)%n,(r+ans)%n);
		r_=max((l+ans)%n,(r+ans)%n);
		l=l_+1;r=r_+1;
		
		if(bel[l]==bel[r]){
			++tim;ans=0;
			for(register int i=l;i<=r;i++){
				if(vis[a[i]]!=tim){
					vis[a[i]]=tim;
					h[a[i]]=i;
				}
				else ans=max(ans,i-h[a[i]]);
			}
			printf("%d\n",ans);
			continue;
		}
		
		if(st[bel[l]]!=l)l_=ed[bel[l]]+1;else l_=l;
		if(ed[bel[r]]!=r)r_=st[bel[r]]-1;else r_=r;
		
		ans=dp[bel[l_]][bel[r_]];++tim;
		for(register int i=l;i<l_;i++){
			ans=max(ans,rmx[i][bel[r_]]-i);
			if(vis[a[i]]!=tim){
				vis[a[i]]=tim;
				h[a[i]]=i;
			}
			else ans=max(ans,i-h[a[i]]);
		}
		for(register int i=r_+1;i<=r;i++){
			if(!lmn[i][bel[l_]])lmn[i][bel[l_]]=n;
			ans=max(ans,i-lmn[i][bel[l_]]);
			if(vis[a[i]]!=tim){
				vis[a[i]]=tim;
				h[a[i]]=i;
			}
			else ans=max(ans,i-h[a[i]]);
		}
		printf("%d\n",ans);
	}
	return 0;
}