代码求调

#include<bits/stdc++.h>
using namespace std;
int n,m;
int q,e;
struct nbfk
{
	int wfirst,wsecond,wthird;
}a[40010];
int c[1010];//区块
int l[40010],r[40010];//区块值
vector < int > d[40010];//同一数出现的下标
int cnt[1010][1010];
int tong[40010];
map < int , int > aa;
bool cmp1(nbfk x,nbfk y)//按初始颜色类别排
{
	return x.wfirst<y.wfirst;
}
bool cmp2(nbfk x,nbfk y)//按输入下标复原
{
	return x.wsecond<y.wsecond;
}
int ef(int ll,int rr)//带区块的二分查找
{
	int w=c[ll],t=c[rr];
	int llll=ll,rrrr=rr;
	int lll=ll,rrr=rr;
	while(llll<rrrr)
	{
		int mid=(llll+rrrr)/2;
		if(d[cnt[w][t]][mid]>rr)
		{
			rrrr=mid-1;
		}
		else
		{
			llll=mid;
		}
	}
	while(lll<rrr)
	{
		int mid=(lll+rrr)/2;
		if(d[cnt[w][t]][mid]<ll)
		{
			lll=mid+1;
		}
		else
		{
			rrr=mid;
		}
	}
	return rrrr-lll+1;
}
int eff(int ll,int rr,int k)//不带区块的二分查找
{
	int llll=ll,rrrr=rr;
	int lll=ll,rrr=rr;
	while(llll<rrrr)
	{
		int mid=(llll+rrrr)/2;
		if(d[a[k].wthird][mid]>rr)
		{
			rrrr=mid-1;
		}
		else
		{
			llll=mid;
		}
	}
	while(lll<rrr)
	{
		int mid=(lll+rrr)>>1;
		if(d[a[k].wthird][mid]<ll)
		{
			lll=mid+1;
		}
		else
		{
			rrr=mid;
		}
	}
	return rrrr-lll+1;
}
int main()
{
	cin>>n>>m;
	int t=sqrt(n);//每块长度
	int len=(n+t-1)/t;//分成len个块
	for(int i=1;i<=n;++i)//输入
	{
		cin>>a[i].wfirst;//原始值
		a[i].wsecond=i;//标记
	}
	sort(a+1,a+n+1,cmp1);//按第一次输入值排序
	int wcolor=1;//颜色种类
	a[1].wthird=wcolor;//颜色离散化
	aa[wcolor]=a[1].wfirst;
	for(int i=2;i<=n;++i)//颜色离散化
	{
		if(a[i].wfirst!=a[i-1].wfirst)
		{
			wcolor++;
		}
		a[i].wthird=wcolor;
		aa[wcolor]=a[i].wfirst;
	}//map aa[wcolor]保存每个颜色对应的实际值
	sort(a+1,a+n+1,cmp2);//复原
	int qujian=1;
	for(int i=0;i<len;)
	{
		l[qujian]=i*t+1;
		r[qujian]=(i+1)*t;
		for(int j=i*t+1;j<=(i+1)*t;++j)
		{
			c[j]=qujian;
		}
		i++;
		qujian++;//区间标记
	}
	for(int i=1;i<=n;++i)
		d[a[i].wthird].push_back(i);//植入离散化后颜色的下标
	for(int i=1;i<=len;++i)
	{
		int y=i;//当前枚举到的区间
		int maxn=-1;
		for(int j=l[i];j<=n;++j)
		{
			if(a[j].wthird==0)
				break;
			tong[a[j].wthird]++;//记录离散化颜色
//			cout<<j<<" "<<a[j].wthird<<" "<<tong[a[j].wthird]<<endl;
//			cout<<"       "<<maxn<<" "<<cnt[i][y]<<endl;
			if(tong[a[j].wthird]==maxn&&a[j].wthird!=0)//颜色最优
				if(a[j].wthird<cnt[i][y])
					cnt[i][y]=a[j].wthird;
			if(tong[a[j].wthird]>maxn)//更新
			{
//				cout<<tong[a[j].wthird]<<" "<<maxn<<endl;
				maxn=tong[a[j].wthird];
				cnt[i][y]=a[j].wthird;
			}
//			cout<<"       "<<maxn<<" "<<cnt[i][y]<<endl;
			if(cnt[i][y]==0)
			{
				cnt[i][y]=cnt[i][y-1];
			}
			if(j==r[y])
				y++;//下一个区间
		}
		memset(tong,0,sizeof(tong));//重置数组
	}
//	cout<<endl<<endl;
//	for(int i=1;i<=n;++i)
//	{
//		cout<<i<<" "<<a[i].wfirst<<" "<<a[i].wsecond<<" "<<a[i].wthird<<endl;
//	}
//	cout<<endl;
//	for(int i=1;i<=len;++i)
//	{
//		cout<<l[i]<<" "<<r[i]<<endl;
//	}
//	cout<<endl;
//	for(int i=1;i<=len;++i)
//	{
//		for(int j=i;j<=len;++j)
//		{
//			cout<<i<<" "<<j<<" "<<cnt[i][j]<<endl;
//		}
//	}
//	for(int i=1;i<=n;++i)
//	{
//		cout<<aa[i]<<" ";
//	}
//	cout<<endl;
//	return 0;
	int qwertyuiop=0;
	for(int i=0;i<m;++i)
	{
		cin>>q>>e;//左右下标
		q=((q+qwertyuiop-1)%n)+1;
		e=((e+qwertyuiop-1)%n)+1;
		if(q>e)
		{
			int u=q;
			q=e;
			e=u;
		}
		int w=c[q],t=c[q];//当前下标的两个区间
		if(w==t||t-w==1)//在同一区块内或两个相邻的区块
		{
			int maxn=0,kinds=0;
			for(int i=q;i<=e;++i)//朴素
			{
				tong[a[i].wthird]++;
				if(tong[a[i].wthird]==maxn)
				{
					if(kinds>a[i].wthird)
					{
						kinds=a[i].wthird;
					}
				}
				if(tong[a[i].wthird]>maxn)
				{
					maxn=tong[a[i].wthird];
					kinds=a[i].wthird;
				}
			}
			cout<<aa[kinds]<<endl;
			qwertyuiop=aa[kinds];
		}
		else//不在同一区块
		{
			int maxn=0,kinds=0;//分别是出现最大次数和种类
			tong[cnt[w][t]]=ef(q,e);//区间先判断
			maxn=tong[cnt[w][t]];//记录次数
			kinds=cnt[w][t];//记录种类
			for(int k=q;k<=r[q];++k)//扫左边
			{
				if(!tong[a[k].wthird])//若没查询过则二分查找
					tong[a[k].wthird]=eff(q,e,k);
				if(tong[a[k].wthird]==maxn)//找编号最小
				{
					if(kinds>a[k].wthird)
						kinds=a[k].wthird;
				}
				if(tong[a[k].wthird]>maxn)//更新变量
				{
					maxn=tong[a[k].wthird];
					kinds=a[k].wthird;
				}
			}
			for(int k=l[e];k<=e;++k)//扫右边
			{
				if(!tong[a[k].wthird])//若没查询过则二分查找
					tong[a[k].wthird]=eff(q,e,k);
				if(tong[a[k].wthird]==maxn)
				{
					if(kinds>a[k].wthird)
						kinds=a[k].wthird;
				}
				if(tong[a[k].wthird]>maxn)
				{
					maxn=tong[a[k].wthird];
					kinds=a[k].wthird;
				}
			}
			cout<<aa[kinds]<<endl;
			qwertyuiop=aa[kinds];
		}
		memset(tong,0,sizeof(tong));//重置数组
	}
	return 0;
}