BZOJ 2724 [Violet 6]蒲公英分块

2019-11-06 08:45:30

字体：大中小

来源：转载

供稿：网友

题目大意：有n个数，给出m个询问，求[l,r]的众数，强制在线

经典的区间众数问题。众数不满足区间加法，线段树这种数据结构就失去了作用。

那么就暴力统计每一个区间的众数，时间复杂度O(mn)，TLE

于是采用分块的思想优化，将区间分成sqrt(n)块，预处理每个块的信息，包含一整块的直接利用预处理的信息；不在一整块的暴力统计。

众数只可能产生在 区间内所有完整的块合在一起的大块的众数 与 不完整的块的数 中。所以这道题需要统计每两个块之间的众数与某个数在每一块的前缀和。按照上面的思想处理即可。分块有一些细节需要注意，写的不好会很麻烦。详见代码。

#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#define N 40005#define pb push_backusing namespace std;int n,m,block_size,block_cnt,top,block[N],a[N],b[N],cnt[N],mode[205][205],sum[N][205];int main() { scanf("%d%d",&n,&m); block_size=floor(sqrt(n))+1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; block[i]=(i-1)/block_size+1; ///预处理每个位置属于哪个块 } block_cnt=block[n]; ///离散化 sort(b+1,b+1+n); top=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+top,a[i])-b; ///预处理 for(int i=1;i<=block_cnt;i++) { int now_mode=0; for(int j=(i-1)*block_size+1;j<=n;j++) { cnt[a[j]]++; if(cnt[a[j]]>cnt[now_mode] || cnt[a[j]]==cnt[now_mode] && a[j]<now_mode) now_mode=a[j]; mode[i][block[j]]=now_mode; } ///在数据范围特别大时最好不要用memset memset(cnt,0,sizeof cnt); } for(int i=1;i<=n;i++) sum[a[i]][block[i]]++; for(int i=1;i<=top;i++) for(int j=1;j<=block_cnt;j++) sum[i][j]+=sum[i][j-1]; int ans=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 now_mode; if(block[r]-block[l]<2) { ///没有完整的块 now_mode=0; for(int i=l;i<=r;i++) { cnt[a[i]]++; if(cnt[a[i]]>cnt[now_mode] || cnt[a[i]]==cnt[now_mode] && a[i]<now_mode) now_mode=a[i]; } memset(cnt,0,sizeof cnt); } else { ///包含完整的块 now_mode=mode[block[l]+1][block[r]-1]; int ed=block[l]*block_size; for(int i=l;i<=ed;i++) { cnt[a[i]]++; int PRe=sum[a[i]][block[r]-1]-sum[a[i]][block[l]],now=sum[now_mode][block[r]-1]-sum[now_mode][block[l]]; if(cnt[a[i]]+pre>cnt[now_mode]+now || cnt[a[i]]+pre==cnt[now_mode]+now && a[i]<now_mode) now_mode=a[i]; } int st=(block[r]-1)*block_size+1; for(int i=st;i<=r;i++) { cnt[a[i]]++; int pre=sum[a[i]][block[r]-1]-sum[a[i]][block[l]],now=sum[now_mode][block[r]-1]-sum[now_mode][block[l]]; if(cnt[a[i]]+pre>cnt[now_mode]+now || cnt[a[i]]+pre==cnt[now_mode]+now && a[i]<now_mode) now_mode=a[i]; } memset(cnt,0,sizeof cnt); } ans=b[now_mode]; printf("%d/n",ans); } return 0;}

上一篇：不是技术牛人，如何拿到国内IT巨头的Offer

下一篇：图说设计模式