【洛谷4168】[Violet]蒲公英

题面

分析

求区间众数,比较好的分块题。

首先一眼发现是强制在线,以及如果要用桶来统计一个数字的数量,显然需要离散化。

发现[l,r]区间的众数只可能是[l,r]之间的块儿的众数或者是两边单独剩的部分中出现过的数。

那我们的范围大大缩小,首先保存每一块的众数,然后对每个数字建立个vector去存它出现的位置,用于查两头零散的部分的元素个数。

可以二分查找两头位置,相减即这段元素个数。

现在需要再算一下块儿的数量T ,预处理是 N*T的 ,询问是 M* N/T *logN的

N如果开根号T在200多就是1e7级别的运算次数

然而这样写挂了,只能吸氧苟活...所以不能所以分块题都随手开根号啊!!!

所以开始玄学优化常数,L,R,pos这些能少预处理的就少预处理把。

把块的数量取到50个是就过了。。也别用map之类的,常数大。。

总之很难解释,分块的时间复杂度真的好玄学,可以自行对比一下两份代码。

不吸氧情况下前一份35000ms,后一份20000ms(20个点,单点限制2000ms)

 

代码

吸氧版

  1. // luogu-judger-enable-o2  
  2. #include<bits/stdc++.h>  
  3. using namespace std;  
  4. #define X 202  
  5. #define N 40004  
  6. #define M 50005  
  7. int n,m,id,maxx;  
  8. int a[N],z[X][X],num[N],cnt[N],pos[N],L[N],R[N];  
  9. vector<int>v[N];  
  10. map<int,int>mp;  
  11.   
  12. void init()  
  13. {  
  14.     int t=sqrt(n);  
  15.     for(int i=1;i<=t;i++)L[i]=(i-1)*t+1,R[i]=i*t;  
  16.     if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;  
  17.     for(int i=1;i<=t;i++)  
  18.         for(int j=L[i];j<=R[i];j++)  
  19.             pos[j]=i;  
  20.     for(int i=1;i<=t;i++)  
  21.     {  
  22.         int maxx=0,tmp=0;  
  23.         memset(cnt,0,sizeof(cnt));  
  24.         for(int j=L[i];j<=n;j++)  
  25.         {  
  26.             cnt[a[j]]++;  
  27.             int p=pos[j];  
  28.             if(cnt[a[j]]>maxx||(cnt[a[j]]==maxx&&num[a[j]]<num[tmp]))  
  29.                 maxx=cnt[a[j]],tmp=a[j];  
  30.             z[i][p]=tmp;  
  31.         }  
  32.     }  
  33. }  
  34.   
  35. inline int cal(int k,int l,int r)  
  36. {  
  37.     return upper_bound(v[k].begin(),v[k].end(),r)-lower_bound(v[k].begin(),v[k].end(),l);  
  38. }  
  39.   
  40. int query(int l,int r)  
  41. {  
  42.     int tmp,ret=0,maxx=0,p=pos[l],q=pos[r];  
  43.     if(p==q)  
  44.     {  
  45.         for(int i=l;i<=r;i++)  
  46.         {  
  47.             tmp=cal(a[i],l,r);  
  48.             if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))  
  49.                 maxx=tmp,ret=a[i];  
  50.         }  
  51.     }  
  52.     else  
  53.     {  
  54.         ret=z[p+1][q-1];  
  55.         maxx=cal(ret,l,r);  
  56.         for(int i=l;i<=R[p];i++)  
  57.         {  
  58.             tmp=cal(a[i],l,r);  
  59.             if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))  
  60.                 maxx=tmp,ret=a[i];  
  61.         }  
  62.         for(int i=L[q];i<=r;i++)  
  63.         {  
  64.             tmp=cal(a[i],l,r);  
  65.             if(tmp>maxx||(tmp==maxx&&num[a[i]]<num[ret]))  
  66.                 maxx=tmp,ret=a[i];  
  67.         }  
  68.     }  
  69.     return ret;  
  70. }  
  71.   
  72. int main()  
  73. {  
  74.     scanf("%d%d",&n,&m);  
  75.     for(int i=1;i<=n;i++)  
  76.     {  
  77.         scanf("%d",&a[i]);  
  78.         if(!mp[a[i]])  
  79.         {  
  80.             mp[a[i]]=++id;  
  81.             num[id]=a[i];  
  82.         }   
  83.         a[i]=mp[a[i]];  
  84.         v[a[i]].push_back(i);  
  85.     }  
  86.     init();  
  87.     while(m--)  
  88.     {  
  89.         int l,r,x;  
  90.         scanf("%d%d",&l,&r);  
  91.         l=(l+x-1)%n+1,r=(r+x-1)%n+1;  
  92.         if(l>r)swap(l,r);  
  93.         x=num[query(l,r)];  
  94.         printf("%d ",x);  
  95.     }  
  96. }  

吸氧版

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define X 4040  
  4. #define N 100020  
  5. int n,t,m,ques,a[N],pos[N],f[X][X],b[N],ans;  
  6. int cnt[N];  
  7. vector<int> v[N];  
  8. int L(int k){ return (k-1)*t+1; }  
  9. int R(int k){ return min(n,k*t); }  
  10. void init(int num)  
  11. {  
  12.     int now=0,ans=0;  
  13.     memset(cnt,0,sizeof(cnt));  
  14.     for(int i=L(num);i<=n;i++)  
  15.     {  
  16.         cnt[a[i]]++;   
  17.         if(cnt[a[i]]>ans||(cnt[a[i]]==ans&&a[i]<now))  
  18.             now=a[i],ans=cnt[a[i]];  
  19.         f[num][pos[i]]=now;   
  20.     }   
  21. }  
  22.   
  23. int cal(int l,int r,int x)  
  24. {   
  25.     return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);  
  26. }   
  27.   
  28. int query(int l,int r)  
  29. {  
  30.     int p=pos[l],q=pos[r];  
  31.     int now=f[p+1][q-1],ans=cal(l,r,now),tmp;  
  32.     for(int i=l;i<=min(r,R(p));i++)  
  33.     {   
  34.         tmp=cal(l,r,a[i]);  
  35.         if(tmp>ans||(tmp==ans&&a[i]<now)){ ans=tmp; now=a[i]; }  
  36.     }   
  37.     if(p==q) return now;  
  38.     for(int i=L(q);i<=r;i++)  
  39.     {   
  40.         tmp=cal(l,r,a[i]);  
  41.         if(tmp>ans||(tmp==ans&&a[i]<now)){ ans=tmp; now=a[i]; }  
  42.     }   
  43.     return now;   
  44. }  
  45.   
  46. int main(){  
  47.     scanf("%d%d",&n,&m),t=50;  
  48.     for(int i=1;i<=n;i++)  
  49.         scanf("%d",&a[i]),pos[i]=(i-1)/t+1,b[i]=a[i];  
  50.     sort(b+1,b+n+1);   
  51.     int n0=unique(b+1,b+n+1)-(b+1);  
  52.     for(int i=1;i<=n;i++)  
  53.     {   
  54.         a[i]=lower_bound(b+1,b+n0+1,a[i])-b;   
  55.         v[a[i]].push_back(i);  
  56.     }   
  57.     for(int i=1;i<=pos[n];i++) init(i);  
  58.     for(int i=1;i<=m;i++)  
  59.     {   
  60.         int l,r;  
  61.         scanf("%d%d",&l,&r);  
  62.         l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;  
  63.         if(l>r) swap(l,r);   
  64.         ans=b[query(l,r)],printf("%d ",ans);  
  65.     }  
  66. }  
原文地址:https://www.cnblogs.com/NSD-email0820/p/9845675.html