题面
分析
求区间众数，比较好的分块题。
首先一眼发现是强制在线，以及如果要用桶来统计一个数字的数量，显然需要离散化。
发现[l,r]区间的众数只可能是[l,r]之间的块儿的众数或者是两边单独剩的部分中出现过的数。
那我们的范围大大缩小，首先保存每一块的众数，然后对每个数字建立个vector去存它出现的位置，用于查两头零散的部分的元素个数。
可以二分查找两头位置，相减即这段元素个数。
现在需要再算一下块儿的数量T ，预处理是 N*T的 ，询问是 M* N/T *logN的
T如果开根号在200多就是1e7左右的运算次数
然而这样写挂了，只能吸氧苟活...所以不能所以分块题都随手开根号啊！！！
所以开始玄学优化常数，L,R，pos这些能少预处理的就少预处理把。
把块的数量取到50个是就过了。。也别用map之类的，常数大。。
总之很难解释，分块的时间复杂度真的好玄学，可以自行对比一下两份代码。
不吸氧情况下前一份35000ms，后一份20000ms(20个点，单点限制2000ms)
代码
吸氧版
-
- #include<bits/stdc++.h>
- using namespace std;
- #define X 202
- #define N 40004
- #define M 50005
- int n,m,id,maxx;
- int a[N],z[X][X],num[N],cnt[N],pos[N],L[N],R[N];
- vector<int>v[N];
- map<int,int>mp;
-
- void init()
- {
- int t=sqrt(n);
- for(int i=1;i<=t;i++)L[i]=(i-1)*t+1,R[i]=i*t;
- if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
- for(int i=1;i<=t;i++)
- for(int j=L[i];j<=R[i];j++)
- pos[j]=i;
- for(int i=1;i<=t;i++)
- {
- int maxx=0,tmp=0;
- memset(cnt,0,sizeof(cnt));
- for(int j=L[i];j<=n;j++)
- {
- cnt[a[j]]++;
- int p=pos[j];
- if(cnt[a[j]]>maxx||(cnt[a[j]]==maxx&&num[a[j]]<num[tmp]))
- maxx=cnt[a[j]],tmp=a[j];
- z[i][p]=tmp;
- }
- }
- }
-
- inline int cal(int k,int l,int r)
- {
- return upper_bound(v[k].begin(),v[k].end(),r)-lower_bound(v[k].begin(),v[k].end(),l);
- }
-
- int query(int l,int r)
- {
- int tmp,ret=0,maxx=0,p=pos[l],q=pos[r];
- if(p==q)
- {
- for(int i=l;i<=r;i++)
- {
- tmp=cal(a[i],l,r);
- if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))
- maxx=tmp,ret=a[i];
- }
- }
- else
- {
- ret=z[p+1][q-1];
- maxx=cal(ret,l,r);
- for(int i=l;i<=R[p];i++)
- {
- tmp=cal(a[i],l,r);
- if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))
- maxx=tmp,ret=a[i];
- }
- for(int i=L[q];i<=r;i++)
- {
- tmp=cal(a[i],l,r);
- if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))
- maxx=tmp,ret=a[i];
- }
- }
- return ret;
- }
-
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- if(!mp[a[i]])
- {
- mp[a[i]]=++id;
- num[id]=a[i];
- }
- a[i]=mp[a[i]];
- v[a[i]].push_back(i);
- }
- init();
- while(m--)
- {
- int l,r,x;
- scanf("%d%d",&l,&r);
- l=(l+x-1)%n+1,r=(r+x-1)%n+1;
- if(l>r)swap(l,r);
- x=num[query(l,r)];
- printf("%d\n",x);
- }
- }
不吸氧版
- #include<bits/stdc++.h>
- using namespace std;
- #define X 4040
- #define N 100020
- int n,t,m,ques,a[N],pos[N],f[X][X],b[N],ans;
- int cnt[N];
- vector<int> v[N];
- int L(int k){ return (k-1)*t+1; }
- int R(int k){ return min(n,k*t); }
- void init(int num)
- {
- int now=0,ans=0;
- memset(cnt,0,sizeof(cnt));
- for(int i=L(num);i<=n;i++)
- {
- cnt[a[i]]++;
- if(cnt[a[i]]>ans||(cnt[a[i]]==ans&&a[i]<now))
- now=a[i],ans=cnt[a[i]];
- f[num][pos[i]]=now;
- }
- }
-
- int cal(int l,int r,int x)
- {
- return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);
- }
-
- int query(int l,int r)
- {
- int p=pos[l],q=pos[r];
- int now=f[p+1][q-1],ans=cal(l,r,now),tmp;
- for(int i=l;i<=min(r,R(p));i++)
- {
- tmp=cal(l,r,a[i]);
- if(tmp>ans||(tmp==ans&&a[i]<now)){ ans=tmp; now=a[i]; }
- }
- if(p==q) return now;
- for(int i=L(q);i<=r;i++)
- {
- tmp=cal(l,r,a[i]);
- if(tmp>ans||(tmp==ans&&a[i]<now)){ ans=tmp; now=a[i]; }
- }
- return now;
- }
-
- int main(){
- scanf("%d%d",&n,&m),t=50;
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]),pos[i]=(i-1)/t+1,b[i]=a[i];
- sort(b+1,b+n+1);
- int n0=unique(b+1,b+n+1)-(b+1);
- for(int i=1;i<=n;i++)
- {
- a[i]=lower_bound(b+1,b+n0+1,a[i])-b;
- v[a[i]].push_back(i);
- }
- for(int i=1;i<=pos[n];i++) init(i);
- for(int i=1;i<=m;i++)
- {
- 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);
- ans=b[query(l,r)],printf("%d\n",ans);
- }
- }
【洛谷4168】[Violet]蒲公英
原文：https://www.cnblogs.com/NSD-email0820/p/9845675.html
