Rubi_sama @ 2023-04-09 16:16:16
#include<bits/stdc++.h>
using namespace std;
int n,m,la,t,len,nn;
long long ls3,ls4,bh,ans,ls;
int a[40010],l[210],r[210],b[40010];
long long cnt[40010];
int pos[40010],yuan[40010];
int f[210][210];
long long s[210][40010];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
nn=unique(b+1,b+1+n)-(b+1);
for(int i=1,ls1;i<=n;i++)
{
ls1=lower_bound(b+1,b+1+nn,a[i])-b;
yuan[ls1]=b[ls1];
a[i]=ls1;
}
t=sqrt(n);
len=t;
for(int i=1;i<=t;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
if(r[t]<n)
{
t++;
l[t]=r[t-1]+1;
r[t]=n;
}
for(int i=1;i<=t;i++)
{
for(int j=l[i];j<=r[i];j++)
{
s[i][a[j]]++;
}
for(int j=1;j<=nn+1;j++)
{
s[i][j]+=s[i-1][j];
}
}
for(int i=1;i<=t;i++)
{
for(int j=i;j<=t;j++)
{//i--->j
bh=f[i][j-1];
for(int k=l[j];k<=r[j];k++)
{
if(s[j][a[k]]-s[i-1][a[k]]>s[j][bh]-s[i-1][bh])
{
bh=a[k];
}
if(s[j][a[k]]-s[i-1][a[k]]==s[j][bh]-s[i-1][bh])
{
if(a[k]<bh)
{
bh=a[k];
}
}
}
f[i][j]=bh;
}
}
for(int i=1;i<=t;i++)
{
for(int j=l[i];j<=r[i];j++)
{
pos[j]=i;
}
}
for(int i=1;i<=m;i++)
{
cin>>ls3>>ls4;
ls3=(ls3+la-1)%n+1;
ls4=(ls4+la-1)%n+1;
if(ls3>ls4)
{
swap(ls3,ls4);
}
if(pos[ls4]-pos[ls3]<=3)
{
ans=-1;
for(int j=ls3;j<=ls4;j++)
{
cnt[a[j]]++;
if(ans==-1)
{
ans=cnt[a[j]];
bh=a[j];
}
if(cnt[a[j]]>ans)
{
ans=cnt[a[j]];
bh=a[j];
}
if(cnt[a[j]]==ans)
{
if(a[j]<bh)
{
ans=cnt[a[j]];
bh=a[j];
}
}
}
for(int j=ls3;j<=ls4;j++)
{
cnt[a[j]]=0;
}
printf("%d\n",yuan[bh]);
la=yuan[bh];
}
else
{
bh=f[pos[ls3]+1][pos[ls4]-1];
ans=s[pos[ls4]-1][bh]-s[pos[ls3]][bh];
for(int j=ls3;j<=r[pos[ls3]];j++)
{
cnt[a[j]]++;
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
cnt[a[j]]++;
}
ans+=cnt[bh];
for(int j=ls3;j<=r[pos[ls3]];j++)
{
ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
if(ls>ans)
{
ans=ls;
}
if(ls==ans)
{
if(a[j]<bh)
{
bh=a[j];
}
}
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
if(ls>ans)
{
ans=ls;
}
if(ls==ans)
{
if(a[j]<bh)
{
bh=a[j];
}
}
}
for(int j=ls3;j<=r[pos[ls3]];j++)
{
cnt[a[j]]=0;
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
cnt[a[j]]=0;
}
printf("%d\n",yuan[bh]);
la=yuan[bh];
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}yuan数组存离散前的值
f[i][j]表示从第i个块到第j个块的众数是几
s[i][k]表示前i个块中a[k]有几个
by zzafanti @ 2023-04-10 18:59:40
枚举边角块更新答案的时候更新答案写错了qwq
注释在代码里
提交记录
#include<bits/stdc++.h>
using namespace std;
int n,m,la,t,len,nn;
long long ls3,ls4,bh,ans,ls;
int a[40010],l[210],r[210],b[40010];
long long cnt[40010];
int pos[40010],yuan[40010];
int f[210][210];
long long s[210][40010];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
nn=unique(b+1,b+1+n)-(b+1);
for(int i=1,ls1;i<=n;i++)
{
ls1=lower_bound(b+1,b+1+nn,a[i])-b;
yuan[ls1]=b[ls1];
a[i]=ls1;
}
t=sqrt(n);
len=t;
for(int i=1;i<=t;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
if(r[t]<n)
{
t++;
l[t]=r[t-1]+1;
r[t]=n;
}
for(int i=1;i<=t;i++)
{
for(int j=l[i];j<=r[i];j++)
{
s[i][a[j]]++;
}
for(int j=1;j<=nn+1;j++)
{
s[i][j]+=s[i-1][j];
}
}
for(int i=1;i<=t;i++)
{
for(int j=i;j<=t;j++)
{ //i--->j
bh=f[i][j-1];
for(int k=l[j];k<=r[j];k++)
{
if(s[j][a[k]]-s[i-1][a[k]]>s[j][bh]-s[i-1][bh])
{
bh=a[k];
}
if(s[j][a[k]]-s[i-1][a[k]]==s[j][bh]-s[i-1][bh])
{
if(a[k]<bh)
{
bh=a[k];
}
}
}
f[i][j]=bh;
}
}
for(int i=1;i<=t;i++)
{
for(int j=l[i];j<=r[i];j++)
{
pos[j]=i;
}
}
for(int i=1;i<=m;i++)
{
cin>>ls3>>ls4;
ls3=(ls3+la-1)%n+1;
ls4=(ls4+la-1)%n+1;
if(ls3>ls4)
{
swap(ls3,ls4);
}
if(pos[ls4]-pos[ls3]<=3)
{
ans=-1;
for(int j=ls3;j<=ls4;j++)
{
cnt[a[j]]++;
if(ans==-1)
{
ans=cnt[a[j]];
bh=a[j];
}
if(cnt[a[j]]>ans)
{
ans=cnt[a[j]];
bh=a[j];
}
if(cnt[a[j]]==ans)
{
if(a[j]<bh)
{
ans=cnt[a[j]];
bh=a[j];
}
}
}
for(int j=ls3;j<=ls4;j++)
{
cnt[a[j]]=0;
}
printf("%d\n",yuan[bh]);
la=yuan[bh];
}
else
{
bh=f[pos[ls3]+1][pos[ls4]-1];
ans=s[pos[ls4]-1][bh]-s[pos[ls3]][bh];
for(int j=ls3;j<=r[pos[ls3]];j++)
{
cnt[a[j]]++;
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
cnt[a[j]]++;
}
ans+=cnt[bh];
for(int j=ls3;j<=r[pos[ls3]];j++)
{
ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
if(ls>ans)
{
ans=ls;
bh=a[j]; //HERE
}
if(ls==ans)
{
if(a[j]<bh)
{
ans=ls; //HERE
bh=a[j];
}
}
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
if(ls>ans)
{
ans=ls;
bh=a[j]; //HERE
}
if(ls==ans)
{
if(a[j]<bh)
{
ans=ls; //HERE
bh=a[j];
}
}
}
for(int j=ls3;j<=r[pos[ls3]];j++)
{
cnt[a[j]]=0;
}
for(int j=ls4;j>=l[pos[ls4]];j--)
{
cnt[a[j]]=0;
}
printf("%d\n",yuan[bh]);
la=yuan[bh];
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}by Rubi_sama @ 2023-04-24 20:05:34
@zzafanti 谢谢
by some_side @ 2023-11-16 14:36:31
@zzafanti 这么厉害。qwq