【BZOJ2724】[Violet 6]蒲公英

#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#include <vector>#include <algorithm>using namespace std;const int maxn=40010;int n,m,nm,B,mx,ans;int v[maxn],st[maxn],ref[maxn];int s[810][810];vector<int> pos[maxn];struct node{	int org,val;}num[maxn];bool cmp(node a,node b){	return a.val<b.val;}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}void query(int a,int b,int x){	if(!x||st[x])	return ;	int l=0,r=pos[x].size()-1,mid,c,d;	while(l<r)	{		mid=l+r>>1;		if(pos[x][mid]>=a)	r=mid;		else	l=mid+1;	}	c=r;	l=0,r=pos[x].size();	while(l<r)	{		mid=l+r>>1;		if(pos[x][mid]<=b)	l=mid+1;		else	r=mid;	}	d=l-1,st[x]=d-c+1;	if(st[x]>st[mx]||(st[x]==st[mx]&&x<mx))	mx=x;}int main(){	//freopen("bz2724.in","r",stdin);	n=rd(),m=rd();	int i,j,a,b,c,d;	for(i=0;i<n;i++)	num[i].val=rd(),num[i].org=i;	sort(num,num+n,cmp);	for(i=0;i<n;i++)	{		if(!i||num[i].val>num[i-1].val)	ref[++nm]=num[i].val;		v[num[i].org]=nm;	}	B=int(sqrt(double(n)/log(n)));	for(i=0;i<n;i++)	pos[v[i]].push_back(i);	for(i=0;i*B<n;i++)	{		memset(st,0,sizeof(st));		for(mx=0,j=i*B;j<n;j++)		{			st[v[j]]++;			if(st[v[j]]>st[mx]||(st[v[j]]==st[mx]&&v[j]<mx))	mx=v[j];			s[i][j/B]=mx;		}	}	memset(st,0,sizeof(st));	for(i=1;i<=m;i++)	{		a=(rd()+ans-1+n)%n,b=(rd()+ans-1+n)%n;		if(a>b)	swap(a,b);		c=a/B,d=b/B;		if(c==d)		{			for(mx=0,j=a;j<=b;j++)			{				st[v[j]]++;				if(st[v[j]]>st[mx]||(st[v[j]]==st[mx]&&v[j]<mx))	mx=v[j];			}			ans=ref[mx],printf("%d\n",ans);			for(j=a;j<=b;j++)	st[v[j]]--;			continue;		}		mx=0,query(a,b,s[c+1][d-1]);		for(j=a;j<c*B+B;j++)	query(a,b,v[j]);		for(j=d*B;j<=b;j++)	query(a,b,v[j]);		ans=ref[mx],printf("%d\n",ans);		st[s[c+1][d-1]]=0;		for(j=a;j<c*B+B;j++)	st[v[j]]=0;		for(j=d*B;j<=b;j++)	st[v[j]]=0;	}	return 0;}