洛谷P4168 蒲公英分块处理区间众数模板( 二 ) _生活百科

处理单词询问时间复杂度为n1/2 。
算法整体复杂度为(m+n)*n1/2，即n3/2，可以通过本题。
类似的题目还有洛谷P4135。
#include<bits/stdc++.h>
using namespace std;const int h=40010;const int b_h=210;int len;int get_pos(int x){//得到某个位置所在分块编号 return (x-1)/len+1;}int n,m;int a[h],line[h];int ntot=0,num[h];map<int,int>rk;int tmp[h];int b_mos[b_h][b_h];int b_sum[b_h][h];void get_pre(){ for(int i=1;i<=get_pos(n);i++) for(int j=1;j<=ntot;j++) b_sum[i][j]+=b_sum[i-1][j]; for(int i=1;i<=get_pos(n);i++){ int mx=0; for(int j=i;j<=get_pos(n);j++){ for(int k=(j-1)*len+1;k<=min(j*len,n);k++){ tmp[a[k]]++; if(tmp[a[k]]>tmp[mx]) mx=a[k]; if(!(tmp[a[k]]^tmp[mx])) mx=min(mx,a[k]); } b_mos[i][j]=mx; } for(int j=0;j<=ntot;j++) tmp[j]=0; }}int l,r,lb,rb,lst=0,ans;int get_vio(){ int mx=0; for(int i=l;i<=r;i++){ tmp[a[i]]++; if(tmp[a[i]]>tmp[mx]) mx=a[i]; if(tmp[a[i]]==tmp[mx]) mx=min(mx,a[i]); } for(int i=l;i<=r;i++) tmp[a[i]]--; return mx;}int get_tim(int x){//计算一个数的出现次数 return tmp[x]+b_sum[rb-1][x]-b_sum[lb][x];}int get_q(){ int mx=b_mos[lb+1][rb-1]; for(int i=l;i<=lb*len;i++){ tmp[a[i]]++; if(get_tim(a[i])>get_tim(mx)) mx=a[i]; if(get_tim(a[i])==get_tim(mx)) mx=min(mx,a[i]); } for(int i=(rb-1)*len+1;i<=r;i++){ tmp[a[i]]++; if(get_tim(a[i])>get_tim(mx)) mx=a[i]; if(get_tim(a[i])==get_tim(mx)) mx=min(mx,a[i]); } for(int i=l;i<=lb*len;i++) tmp[a[i]]--; for(int i=(rb-1)*len+1;i<=r;i++) tmp[a[i]]--; return mx;}int main(){ scanf("%d%d",&n,&m); len=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),line[i]=a[i]; sort(line+1,line+n+1); for(int i=1;i<=n;i++)//离散化 if(line[i]!=line[i-1]) rk[line[i]]=++ntot,num[ntot]=line[i]; for(int i=1;i<=n;i++) a[i]=rk[a[i]]; for(int i=1;i<=n;i++) b_sum[get_pos(i)][a[i]]++; get_pre(); for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); l=(l+lst-1)%n+1,r=(r+lst-1)%n+1; if(l>r) swap(l,r); lb=get_pos(l),rb=get_pos(r); if(lb>=rb-1) ans=get_vio(); else ans=get_q(); printf("%d\n",num[ans]),lst=num[ans]; } return 0;}

洛谷P4168 蒲公英分块处理区间众数模板( 二 )

推荐阅读

关于火棘简述火棘

告别2019迎接2020抖音句子大全告别2019迎接2020抖音句子

属虎相冲的属相是什么生肖，属虎与什么生肖相冲

2022吉林养老金上调方案最新消息吉林养老金计算公式2022计算器举例

荒原雪荒原雪狼稿件

塔罗未来结婚对象的特征，我想的人心里想我吗

怎么取消科目一考试预约成功怎么取消科目一考试预约

雅诗兰黛口红怎么样

显卡怎么测试怎样测试显卡性能

黄蚊子是什么蚊子黄蚊子的介绍

江苏儿童新冠疫苗可以和其它疫苗同时接种吗

手机容量不足怎么办教你简单的几招

画苹果核的方法苹果的果核怎么画

年底出生的女孩取名字冬天女孩取名

汽车贴膜有气泡怎么办点模糊汽车贴膜有气泡怎么办

削完芋头皮手痒怎么办削完芋头皮手痒可以怎么办

玉米用量多还是小麦用量多？有什么依据呢？

艾薇儿纸尿裤是什么档次的品牌

运筹帷幄词语解释坐筹帷幄名词解释

京东拼购1200万赏金大街&ensp;收藏店铺最高可领取250京豆

洛谷P4168 蒲公英 分块处理区间众数模板( 二 )

推荐阅读

洛谷P4168 蒲公英分块处理区间众数模板( 二 )