首页 > 代码库 > 【BZOJ2724】[Violet 6]蒲公英 分块+二分
【BZOJ2724】[Violet 6]蒲公英 分块+二分
【BZOJ2724】[Violet 6]蒲公英
Description
.gif)
Input
.gif)
修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
Output
.gif)
Sample Input
6 3
1 2 3 2 1 2
1 5
3 6
1 5
1 2 3 2 1 2
1 5
3 6
1 5
Sample Output
1
2
1
2
1
HINT
.gif)
修正下：
n <= 40000, m <= 50000
题解：分块还是练脑子啊~
结论：一个区间的众数要么是区间中一个块的众数，要么是块外的任意一个数。
这就告诉我们需要预处理出任意两个块之间的所有数的众数，这个可以用离散化+桶+扫一遍实现。
那么对于询问[l,r]我们假设其中最大的连续的块是[ll,rr]，那么我们已知了[ll,rr]中的众数，如何判断[l,ll)，(rr,r]中的数是不是众数呢？
既然已经将所有数离散化了，我们就可以考虑记录每个数出现的位置。我们将每个数出现的位置从左到右用vector存起来，然后查询的时候二分一下，就知道了这个数在[l,r]中出现了多少次，用它来更新答案就行了。
sqrt(n/logn)大法好~
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#include <vector>#include <algorithm>using namespace std;const int maxn=40010;int n,m,nm,B,mx,ans;int v[maxn],st[maxn],ref[maxn];int s[810][810];vector<int> pos[maxn];struct node{ int org,val;}num[maxn];bool cmp(node a,node b){ return a.val<b.val;}int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}void query(int a,int b,int x){ if(!x||st[x]) return ; int l=0,r=pos[x].size()-1,mid,c,d; while(l<r) { mid=l+r>>1; if(pos[x][mid]>=a) r=mid; else l=mid+1; } c=r; l=0,r=pos[x].size(); while(l<r) { mid=l+r>>1; if(pos[x][mid]<=b) l=mid+1; else r=mid; } d=l-1,st[x]=d-c+1; if(st[x]>st[mx]||(st[x]==st[mx]&&x<mx)) mx=x;}int main(){ //freopen("bz2724.in","r",stdin); n=rd(),m=rd(); int i,j,a,b,c,d; for(i=0;i<n;i++) num[i].val=rd(),num[i].org=i; sort(num,num+n,cmp); for(i=0;i<n;i++) { if(!i||num[i].val>num[i-1].val) ref[++nm]=num[i].val; v[num[i].org]=nm; } B=int(sqrt(double(n)/log(n))); for(i=0;i<n;i++) pos[v[i]].push_back(i); for(i=0;i*B<n;i++) { memset(st,0,sizeof(st)); for(mx=0,j=i*B;j<n;j++) { st[v[j]]++; if(st[v[j]]>st[mx]||(st[v[j]]==st[mx]&&v[j]<mx)) mx=v[j]; s[i][j/B]=mx; } } memset(st,0,sizeof(st)); for(i=1;i<=m;i++) { a=(rd()+ans-1+n)%n,b=(rd()+ans-1+n)%n; if(a>b) swap(a,b); c=a/B,d=b/B; if(c==d) { for(mx=0,j=a;j<=b;j++) { st[v[j]]++; if(st[v[j]]>st[mx]||(st[v[j]]==st[mx]&&v[j]<mx)) mx=v[j]; } ans=ref[mx],printf("%d\n",ans); for(j=a;j<=b;j++) st[v[j]]--; continue; } mx=0,query(a,b,s[c+1][d-1]); for(j=a;j<c*B+B;j++) query(a,b,v[j]); for(j=d*B;j<=b;j++) query(a,b,v[j]); ans=ref[mx],printf("%d\n",ans); st[s[c+1][d-1]]=0; for(j=a;j<c*B+B;j++) st[v[j]]=0; for(j=d*B;j<=b;j++) st[v[j]]=0; } return 0;}【BZOJ2724】[Violet 6]蒲公英 分块+二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。