codingwen @ 2023-11-29 20:51:25
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=40010;
int s[210][N],f[210][210];
int a[N],b[N];
int lef[N],righ[N];
int n,m,kkk,sc;
int q[N],t[N];
int dis(int x){
return lower_bound(b+1,b+1+sc,x)-b;
}
void init(){
int cnt=n/kkk;
if(n%kkk)cnt++;
for(int i=1;i<=cnt;i++){
lef[i]=(i-1)*kkk+1;
righ[i]=i*kkk;
}
righ[cnt]=n;
for(int i=1;i<=cnt;i++){
for(int j=lef[i];j<=righ[i];j++){
s[i][a[j]]++;
q[j]=i;
}
for(int j=1;j<=kkk;j++)s[i][j]+=s[i-1][j];
}
for(int i=1;i<=cnt;i++){
for(int j=i;j<=cnt;j++){
int res=f[i][j-1];
for(int k=lef[j];k<=righ[j];k++){
int v1=s[j][res]-s[i-1][res];
int v2=s[j][a[k]]-s[i-1][a[k]];
if(v1<v2)res=a[k];
else if(v1==v2)res=min(res,a[k]);
}
f[i][j]=res;
}
}
}
int fb(int l,int r,int L,int R,int res){
for(int i=l;i<=r;i++) {
int v1=t[a[i]]+s[q[R]-1][a[i]]-s[q[L]][a[i]];
int v2=t[res]+s[q[R]-1][res]-s[q[L]][res];
if(v1>v2)res=a[i];
else if(v1==v2)res=min(res,a[i]);
}
return res;
}
int query(int l,int r){
if(q[r]-q[l]<=1){
for(int i=l;i<=r;i++)t[a[i]]++;
int res=a[l];
for(int i=l+1;i<=r;i++){
if(t[a[i]]>t[res])res=a[i];
else if(t[a[i]]==t[res])res=min(res,a[i]);
}
for(int i=l;i<=r;i++)t[a[i]]=0;
return b[res];
}
for(int i=l;i<=righ[q[l]];i++)t[a[i]]++;
for(int i=lef[q[r]];i<=r;i++)t[a[i]]++;
int ans=f[q[l]+1][q[r]-1];
ans=fb(l,righ[q[l]],l,r,ans);
ans=fb(lef[q[r]],r,l,r,ans);
for(int i=l;i<=righ[q[l]];i++)t[a[i]]=0;
for(int i=lef[q[r]];i<=r;i++)t[a[i]]=0;
return b[ans];
}
signed main(){
cin>>n>>m;
kkk=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
sc=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)a[i]=dis(a[i]);
init();
int x=0;
while(m--){
int l0,r0;
cin>>l0>>r0;
int l=(l0+x-1)%n+1,r=(r0+x-1)%n+1;
if(l>r)swap(l,r);
x=query(l,r);
cout<<x<<endl;
}
return 0;
}by Cjh20120613 @ 2023-11-29 21:21:35
看看我的行不行
#include <cstdio>
#include <cmath>
#include <algorithm>
const int maxn=40000+10;
int a[maxn],b[maxn],s[200+10][maxn],f[200+10][200+10],t[maxn];
int block;
int read()
{
int x=0,p=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if (ch=='-')
p=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*p;
}
int get_block(int u)
{
return (u-1)/block+1;
}
inline int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
int n=read(),m=read();
block=int(sqrt(n));
for (int i=1;i<=n;i++)
b[i]=a[i]=read();
std::sort(b+1, b+1+n);
int sum=std::unique(b+1, b+1+n)-b-1,cnt=(n-1)/block+1;
for (int i=1;i<=n;i++)
a[i]=std::lower_bound(b+1, b+1+sum, a[i])-b;
for (int i=1;i<=cnt;i++)
{
for (int j=block*(i-1)+1;j<=min(block*i, n);j++)
s[i][a[j]]++;
for (int j=1;j<=sum;j++)
s[i][j]+=s[i-1][j];
}
for (int i=1;i<=cnt;i++)
for (int j=i;j<=cnt;j++)
{
int MAX=f[i][j-1];
for (int k=block*(j-1);k<=min(block*j, n);k++)
if ((s[j][a[k]]-s[i-1][a[k]]>s[j][MAX]-s[i-1][MAX])||(s[j][a[k]]-s[i-1][a[k]]==s[j][MAX]-s[i-1][MAX]&&a[k]<MAX))
MAX=a[k];
f[i][j]=MAX;
}
int x=0;
while(m--)
{
int l=(read()+x-1)%n+1,r=(read()+x-1)%n+1;
if (l>r)
std::swap(l, r);
int bl=get_block(l),br=get_block(r),MAX=0;
if (br-bl<=1)/
{
for (int i=l;i<=r;i++)
t[a[i]]++;
for (int i=l;i<=r;i++)
if (t[a[i]]>t[MAX]||(t[a[i]]==t[MAX]&&a[i]<MAX))
MAX=a[i];
for (int i=l;i<=r;i++)//将桶清空
t[a[i]]=0;
}
else
{
for (int i=l;i<=block*bl;i++)
t[a[i]]++;
for (int i=block*(br-1)+1;i<=r;i++)
t[a[i]]++;
MAX=f[bl+1][br-1];
for (int i=l;i<=block*bl;i++)//考虑蓝色部分出现的数是否会成为众数
{
int pre=t[MAX]+s[br-1][MAX]-s[bl][MAX],now=t[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
if (now>pre||(now==pre&&MAX>a[i]))
MAX=a[i];
}
for (int i=block*(br-1)+1;i<=r;i++)
{
int pre=t[MAX]+s[br-1][MAX]-s[bl][MAX],now=t[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
if (now>pre||(now==pre&&MAX>a[i]))
MAX=a[i];
}
for (int i=l;i<=block*bl;i++)//将桶清空
t[a[i]]=0;
for (int i=block*(br-1)+1;i<=r;i++)
t[a[i]]=0;
}
x=b[MAX];
printf("%d\n",x);
}
return 0;
}