大海中的孤帆 @ 2023-11-16 12:57:03
#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;
}