题链:https://www.luogu.org/problemnew/show/P4168
这是一道神仙题
首先分块,答案可能是夹在中间的块或者是两边的数
预处理出任意一段块的众数
再每块用前缀和
每次询问暴力就好了
有点语无伦次,看代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int M=305,N=1e5+5;
int n,m,S,T,a[N],c[N],d[N],t[N];
int Num,ans,f[M][M],s[M][N];
struct A{int x,id; }b[N];
bool cmp(A i,A j){return i.x<j.x; }
int main()
{
scanf("%d%d",&n,&m);
S=sqrt(n);
T=(n%S==0)?n/S:n/S+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i].x);
b[i].id=i;
}
sort(b+1,b+n+1,cmp);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(b[i].x!=b[i-1].x)
cnt++;
a[b[i].id]=cnt;
c[cnt]=b[i].x;
}
for(int i=1;i<=T;i++)
for(int j=(i-1)*S+1;j<=min(i*S,n);j++)
s[i][a[j]]++;
for(int i=1;i<=T;i++)
for(int j=1;j<=cnt;j++)
s[i][j]+=s[i-1][j];
for(int i=1;i<=T;i++)
{
int Mx=0;
Num=0;
for(int j=1;j<=cnt;j++)
{
d[j]=s[i][j]-s[i-1][j];
if(d[j]>Num)
{
Num=d[j];
Mx=j;
}
}
f[i][i]=Mx;
for(int j=i+1;j<=T;j++)
{
for(int k=(j-1)*S+1;k<=min(j*S,n);k++)
{
d[a[k]]++;
if(d[a[k]]>Num||d[a[k]]==Num&&a[k]<Mx)
{
Num=d[a[k]];
Mx=a[k];
}
}
f[i][j]=Mx;
}
}
ans=0;
for(int i=1;i<=cnt;i++)
d[i]=0;
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
if(l>r) swap(l,r);
int lb=(l-1)/S+2,rb=r/S;
if(rb<lb)
{
ans=0; Num=0;
for(int i=l;i<=r;i++)
d[a[i]]++;
for(int i=l;i<=r;i++)
if(d[a[i]]>Num||d[a[i]]==Num&&a[i]<ans)
{
ans=a[i];
Num=d[a[i]];
}
for(int i=l;i<=r;i++)
d[a[i]]=0;
ans=c[ans];
printf("%d\n",ans);
}else
{
for(int i=l;i<=min(n,(lb-1)*S);i++)
t[a[i]]++;
for(int i=rb*S+1;i<=min(n,r);i++)
t[a[i]]++;
ans=f[lb][rb];
Num=t[ans]+s[rb][ans]-s[lb-1][ans];
for(int i=l;i<=min(n,lb*S);i++)
if(t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]]>Num||
t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]]==Num&&a[i]<ans)
{
Num=t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]];
ans=a[i];
}
for(int i=rb*S+1;i<=min(n,r);i++)
if(t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]]>Num||
t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]]==Num&&a[i]<ans)
{
Num=t[a[i]]+s[rb][a[i]]-s[lb-1][a[i]];
ans=a[i];
}
for(int i=l;i<=min(n,(lb-1)*S);i++)
t[a[i]]--;
for(int i=rb*S+1;i<=min(n,r);i++)
t[a[i]]--;
ans=c[ans];
printf("%d\n",ans);
}
}
return 0;
}