题目链接
分析
可以先将 \(a[i]\) 离散化
然后考虑分块
对于询问 \(x,y\), \(x\) 属于 \(p\), \(y\) 属于 \(q\)
当 \(q-p<=1\) 时
直接暴力枚举即可,时间复杂度为 \(O(\sqrt{n})\)
\(else\) 如图
中间为分好块的地方
我们发现, \(ans\) 只可能为中间的众数或两边的的数
对于中间的众数,我们可以预处理出 \(z[i][j]\) 代表块 \(i\) 与块 \(j\) 之间的众数,时间复杂度为 \(O(n\sqrt{n})\)
对于两边的数,由于要考虑它们在中间出现的个数,所以先预处理出 \(cnt[i][j]\) 代表块 \(i\) 前, \(a[j]\) 的个数,时间复杂度为 \(O(n\sqrt{n})\)
再暴力枚举左右两侧,时间复杂度为, \(O(\sqrt{n})\)
所以总时间复杂度为 \(O(n\sqrt{n})\)
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=40005,SN=405;
int id[N],a[N];
struct C{int id,w;}c[N];
bool cmp(C a,C b){return a.w<b.w;}
int fmp[N];
int tot=0;
int z[SN][SN],cnt[SN][N];
int cnt1[N],cnt2[N];
struct NODE{int l,r;}no[SN];
signed main(){
int n,m;
scanf("%lld %lld", &n, &m);
int L=sqrt(n);
for(int i=1;i<=n;i++){
id[i]=(i-1)/L+1;
if(id[i]!=id[i-1]) no[id[i]].l=i;
if(i%L==0) no[id[i]].r=i;
scanf("%lld", &a[i]);
c[i].w=a[i];c[i].id=i;
}
no[id[n]].r=n;
sort(c+1,c+n+1,cmp);//离散化
for(int i=1;i<=n;i++){
if(c[i].w!=c[i-1].w) a[c[i].id]=++tot;
else a[c[i].id]=tot;
fmp[tot]=c[i].w;
}
for(int i=1;i<=n;i++){//预处理前缀和
if(id[i]!=id[i-1]) for(int j=1;j<=tot;j++) cnt[id[i]][j]=cnt[id[i-1]][j];
cnt[id[i]][a[i]]++;
}
for(int i=1;i<=id[n];i++){//预处理众数
int ma=0;
for(int j=i;j<=id[n];j++){
int l=no[j].l,r=no[j].r;
for(int k=l;k<=r;k++){
int d=a[k];
cnt1[d]++;
if(cnt1[d]>cnt1[ma]) ma=d;
else if(cnt1[d]==cnt1[ma]&&fmp[d]<fmp[ma]) ma=d;
}
z[i][j]=ma;
}
for(int j=1;j<=tot;j++) cnt1[j]=0;
}
int ans=0;
for(int i=1;i<=m;i++){
int x,y;scanf("%lld %lld", &x, &y);
x=(x+ans-1)%n+1;y=(y+ans-1)%n+1;if(x>y) swap(x,y);
int p=id[x],q=id[y];
if(p==q||p==q-1){//情况一
ans=0;
for(int j=x;j<=y;j++){
int d=a[j];
cnt2[d]++;
if(cnt2[d]>cnt2[ans]) ans=d;
else if(cnt2[d]==cnt2[ans]&&fmp[d]<fmp[ans]) ans=d;
}
ans=fmp[ans];
printf("%lld\n", ans);
for(int j=x;j<=y;j++) cnt2[a[j]]=0;
}
else{//情况二
p++;q--;
ans=z[p][q];
for(int j=x;j<=no[p-1].r;j++){//左边
int d=a[j];
cnt2[d]++;
if(cnt2[d]+cnt[q][d]-cnt[p-1][d]>cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]) ans=d;
else if(cnt2[d]+cnt[q][d]-cnt[p-1][d]==cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]&&fmp[d]<fmp[ans]) ans=d;
}
for(int j=no[q+1].l;j<=y;j++){//右边
int d=a[j];
cnt2[d]++;
if(cnt2[d]+cnt[q][d]-cnt[p-1][d]>cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]) ans=d;
else if(cnt2[d]+cnt[q][d]-cnt[p-1][d]==cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]&&fmp[d]<fmp[ans]) ans=d;
}
ans=fmp[ans];printf("%lld\n", ans);
//归零
for(int j=x;j<=no[p].l-1;j++) cnt2[a[j]]--;
for(int j=no[q].r+1;j<=y;j++) cnt2[a[j]]--;
}
}
return 0;
}
标签:cnt,int,题解,复杂度,sqrt,Luogu,cnt2,ans,P4168
From: https://www.cnblogs.com/Idtwtei/p/17796613.html