「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)
HINT
.gif)
修正下：
n <= 40000, m <= 50000
题解
在线区间众数的分块做法比较多，这里提供一个思路：
首先离散化一下比较方便。
最初可能会有一个想法，是不是众数只可能是完整的块的众数，或者不完整的块出现的数呢？显然很容易得出反例。
应该是完整的所有块的众数，和不完整块中出现的数。
所以我们可以预处理f(i,j)表示第 i 块到第 j 块的众数（枚举 i 开个桶扫一遍）。
那么只要能快速得出一个数在某个区间内出现次数即可，每次只要比较至多2√n+1个元素的出现次数，这题就解决了。
由于没有修改，只要离散化以后，给每个数 x 开个vector，按顺序存下 x 出现的位置，每次询问 x 时把区间的左右端点放进对应 vector 二分一下即可。
根据均值不等式，可以算出分块大小大概是√(n/logn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 10007 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,blo,id; int v[50005],bl[50005]; int f[505][505]; map<int,int>mp; int val[50005],cnt[50005]; vector<int>ve[50005]; void pre(int x) { memset(cnt,0,sizeof(cnt)); int mx=0,ans=0; for(int i=(x-1)*blo+1;i<=n;i++) { cnt[v[i]]++; int t=bl[i]; if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans])) ans=v[i],mx=cnt[v[i]]; f[x][t]=ans; } } int query(int l,int r,int x) { int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l); return t; } int query(int a,int b) { int ans,mx; ans=f[bl[a]+1][bl[b]-1]; mx=query(a,b,ans); for(int i=a;i<=min(bl[a]*blo,b);i++) { int t=query(a,b,v[i]); if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t; } if(bl[a]!=bl[b]) for(int i=(bl[b]-1)*blo+1;i<=b;i++) { int t=query(a,b,v[i]); if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t; } return ans; } int main() { n=read();m=read(); blo=200; int ans=0; for(int i=1;i<=n;i++) { v[i]=read(); if(!mp[v[i]]) { mp[v[i]]=++id; val[id]=v[i]; } v[i]=mp[v[i]]; ve[v[i]].push_back(i); } for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1; for(int i=1;i<=bl[n];i++)pre(i); for(int i=1;i<=m;i++) { int a=read(),b=read(); a=(a+ans-1)%n+1;b=(b+ans-1)%n+1; if(a>b)swap(a,b); ans=val[query(a,b)]; printf("%d\n",ans); } return 0; } |
计数器 9786905
OI 课件=>
OI 课件=>
黄学长百度hi挂掉了……求更新题解~~~
已补
妙