区间众数问题一般是指给定一个序列，每次询问 \([l,r]\) 区间的众数是几的问题。

当然了，带修改的区间众数问题比较难搞，这里不展开讨论，只研究静态的区间众数问题。

众数并不满足区间“可加性”，这导致它让全部基于二分的数据结构直接 gg （比如线段树、树状数组等），所以大部分研究区间众数的算法都是基于分块。

目前我知道的最优秀的求解区间众数的算法是数据结构带师 lxl 在 Ynoi 毒瘤模拟赛给出的 \(O(n^{1.485})\) 的在线算法。不过我是不会，今天只介绍一个 \(O(n^{1.5})\) 的离线做法和以及一个 \(O(n^{\frac 5 3})\) 的在线做法。

直接结合例题分析吧。

题目链接：Link

题目描述：

给定一个长度为 \(N\) 的序列，有 \(q\) 次询问，每次询问一个区间 \([l,r]\) 的众数出现的次数。

Solution：

这题比区间众数问题简化了一点，我们只需要求出众数出现的次数就行了，减少了一些麻烦。

看到“众数”直接考虑分块就行了。这题不强制在线，我选择了离线的莫队算法。发现向答案区间添加一个数实现比较简单，可以顺便更新众数出现次数。而删除操作比较操蛋，如果我们正好删除了区间的众数之一，可能导致众数改变，而我们在不扫描值域的情况下，不能得知新的众数出现次数是多少。

emmmm… 这不就是裸的回滚莫队吗？

回滚莫队我之前讲过，这是模板题所以不再详细注释代码了，想看详细注释的朋友移步这里。

Code：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  7. //using namespace std;
  8. //Rool Back CaptianMo\'s Algorithm
  10. #define int long long
  11. const int maxn=200005;
  13. template <typename _T>
  14. inline _T const& read(_T &x){
  15.   x=0;int f=1;
  16.   char ch=getchar();
  17.   while(!isdigit(ch)){
  18.     if(ch==\'-\')
  19.       f=-1;
  20.     ch=getchar();
  21.   }
  22.   while(isdigit(ch)){
  23.     x=(x<<3)+(x<<1)+ch-\'0\';
  24.     ch=getchar();
  25.   }
  26.   return x*=f;
  27. }
  29. int n,q,len,tot;
  30. int A[maxn],B[maxn];
  31. int bel[maxn],L[maxn],R[maxn];
  33. struct Node{
  34.   int l,r,org;
  35. };
  37. struct Node query[maxn];
  38. inline bool operator < (const Node a,const Node b){
  39.   return bel[a.l]!=bel[b.l]?bel[a.l]<bel[b.l]:a.r<b.r;
  40. }
  42. void Init(){
  43.   read(n),read(q);
  44.   len=(int)std::sqrt(n);
  45.   tot=n/len;
  46.   for(int i=1;i<=tot;++i){
  47.     if(i*len>n) break;
  48.     L[i]=(i-1)*len+1;
  49.     R[i]=i*len;
  50.   }
  51.   if(R[tot]<n)
  52.     tot++,L[tot]=R[tot-1]+1,R[tot]=n;
  53.   for(int i=1;i<=n;++i){
  54.     bel[i]=(i-1)/len+1;
  55.     B[i]=read(A[i]);
  56.   }
  57.   std::sort(B+1,B+1+n);
  58.   int m=std::unique(B+1,B+1+n)-B-1;
  59.   for(int i=1;i<=n;++i)
  60.     A[i]=std::lower_bound(B+1,B+m+1,A[i])-B;
  61.   for(int i=1;i<=q;++i)
  62.     read(query[i].l),read(query[i].r),query[i].org=i;
  63. }
  65. int cnt[maxn],cnt1[maxn];
  66. int ans;
  68. inline void add(const int i){
  69.   cnt[A[i]]++;
  70.   ans=ans>cnt[A[i]]?ans:cnt[A[i]];
  71. }//核心，添加的同时更新众数出现次数
  73. inline void del(const int i){
  74.   cnt[A[i]]--;//直接删除，不考虑影响
  75. }
  77. int ans1[maxn];
  79. signed main(){
  80.   Init();
  81.   std::sort(query+1,query+q+1);
  82.   int l=R[bel[query[1].l]]+1,r=R[bel[query[1].l]],last=bel[query[1].l];
  83.   for(int i=1;i<=q;++i){
  84.     if(bel[query[i].l]==bel[query[i].r]){
  85.       int tmp=0;
  86.       for(int j=query[i].l;j<=query[i].r;++j)
  87.         cnt1[A[j]]++;
  88.       for(int j=query[i].l;j<=query[i].r;++j)
  89.         tmp=tmp>cnt1[A[j]]?tmp:cnt1[A[j]];
  90.       for(int j=query[i].l;j<=query[i].r;++j)
  91.         cnt1[A[j]]--;
  92.       ans1[query[i].org]=tmp;
  93.       continue;
  94.     }
  95.     if(bel[query[i].l]!=last){
  96.       while(r>R[bel[query[i].l]])
  97.         del(r--);
  98.       while(l<R[bel[query[i].l]]+1)
  99.         del(l++);
  100.       ans=0,last=bel[query[i].l];
  101.     }
  102.     while(r<query[i].r)
  103.       add(++r);
  104.     int tmp=ans,l1=l;
  105.     while(l1>query[i].l)
  106.       add(--l1);
  107.     ans1[query[i].org]=ans;
  108.     while(l1<l)//回滚还原
  109.       del(l1++);
  110.     ans=tmp;
  111.   }
  112.   for(int i=1;i<=q;++i)
  113.     printf("%d\n",ans1[i]);
  114.   return 0;
  115. }

题目链接：Link

题目描述：

给定一个长度为 \(N\) 的序列，有 \(M\) 次询问，每次询问一个区间 \([l,r]\) 的众数是多少。如果有多个数可以作为区间众数，那么输出最小的那一个。输入数据经过加密，强制在线。

Solution：

看到“众数”直接考虑分块就行了。这题强制在线，把莫队也废了，只能考虑普通的分块。

考虑每个询问 \([l,r]\) ，设 \(l\) 属于第 \(p\) 块，\(r\) 属于第 \(q\) 块。分块一般把一段区间 \([l,r]\) 分成 3 部分：

  1. 开头的零散段 \([l,L)\) ；
  2. 中间的由整块构成的段 \([L,R]\) ；
  3. 结尾的零散段 \((R,r]\) ；

根据分块“大段维护，局部暴力”的思想，应该重点考虑如何维护 \([L,R]\) ，剩下的交给暴力。

在区间求和问题中，分块预处理了每块的区间和。查询时零散段暴力求和，再加上预处理好的区间和，就得到了答案。受此启发，感觉上也可以预处理每块的众数是几。但是区间和可以相加得到更长区间的区间和，也就是区间和满足“可加性”。众数不满足可加性，所以预处理不能只处理每块的众数，要把所有以块的端点为端点的区间 \([L,R]\) 的众数预处理出来。

现在考虑零散段暴力。零散段中的元素可能导致最终答案改变，所以还要记下来中间整段中每个元素出现了多少次（开桶，记为 \(cnt_{L,R}\) ）。直接把两段零散段的元素加入桶中，同时更新众数的值。加入完零散段元素之后得到这次询问的答案。记录答案之后，要把加入的元素再删掉，恢复原来的 \(cnt_{L,R}\) 的环境，以便下次使用（这不是有点像回滚莫队吗？）。

思路口胡完了，来分析一下时空复杂度吧（设块长为 \(T\) ）。

  • 预处理了 \(T\) 个块，每个块长度约为 \(N\) ，预处理时间复杂度 \(NT^2\) ；
  • 零散段长度 \(\frac N T\) ，每次暴力处理，回答询问时间复杂度 \(\frac {MN} T\) ；
  • 每一个块内开了长度为 \(N\) 的桶，空间复杂度 \(NT^2\) ；

总复杂度 \(O(NT^2+\frac {NM} T)\) ，空间为 \(O(NT^2)\) 。不妨设 \(M,N\) 同数量级，得方程：

\[NT^2=\frac {NM} T
\]

解得当 \(T=\sqrt[3] N\) 时，算法最快，时间复杂度、空间复杂度都约为 \(O(N^{\frac 5 3})\) 。

Code：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  7. //using namespace std;
  8. //Online Solve Range Mode Problem
  10. #define ll long long
  11. const int maxn=40005;
  13. template <typename _T>
  14. inline _T const& read(_T &x){
  15.   x=0;int f=1;
  16.   char ch=getchar();
  17.   while(!isdigit(ch)){
  18.     if(ch==\'-\')
  19.       f=-1;
  20.     ch=getchar();
  21.   }
  22.   while(isdigit(ch)){
  23.     x=(x<<3)+(x<<1)+ch-\'0\';
  24.     ch=getchar();
  25.   }
  26.   return x*=f;
  27. }
  29. int n,m,len,tot;
  30. int A[maxn],B[maxn];
  31. int bel[maxn],L[maxn],R[maxn];
  33. int cnt[40][40][maxn];//cnt[L][R][0] refers to Range(L,R)\'s mode appers times.
  34. int mode[40][40];
  35. int cnt1[maxn];
  37. inline void add(const int _L,const int _R,const int i){//添加一个数，更新当前区间众数和众数出现的次数
  38.   cnt[_L][_R][A[i]]++;
  39.   mode[_L][_R] = cnt[_L][_R][A[i]] > cnt[_L][_R][0] ? B[A[i]] : mode[_L][_R];
  40.   mode[_L][_R] = cnt[_L][_R][A[i]] == cnt[_L][_R][0] && B[A[i]] < mode[_L][_R] ? B[A[i]] : mode[_L][_R];
  41.   cnt[_L][_R][0] = cnt[_L][_R][A[i]] > cnt[_L][_R][0] ? cnt[_L][_R][A[i]] : cnt[_L][_R][0];
  42. }
  44. inline void del(const int _L,const int _R,const int i){
  45.   cnt[_L][_R][A[i]]--;
  46. }
  48. void Init(){
  49.   read(n),read(m);
  50.   len=n/pow(n,0.3333333333);
  51.   tot=n/len;
  52.   // printf("len=%d tot=%d",len,tot);
  53.   for(int i=1;i<=tot;++i){
  54.     if(i*len>n) break;
  55.     L[i]=(i-1)*len+1;
  56.     R[i]=i*len;
  57.   }
  58.   if(R[tot]<n)
  59.     tot++,L[tot]=R[tot-1]+1,R[tot]=n;
  60.   for(int i=1;i<=n;++i){
  61.     bel[i]=(i-1)/len+1;
  62.     B[i]=read(A[i]);
  63.   }//原题值域较大，需要离散化
  64.   std::sort(B+1,B+1+n);
  65.   int l=std::unique(B+1,B+n+1)-B-1;
  66.   for(int i=1;i<=n;++i)
  67.     A[i]=std::lower_bound(B+1,B+1+l,A[i])-B;
  68. //枚举区间L,R，进行预处理
  69.   for(int i=1;i<=tot;++i)
  70.     for(int j=i;j<=tot;++j){
  71.       for(int k=L[i];k<=R[j];++k)
  72.         add(i,j,k); 
  73. }
  74.     
  75. int ans;//记录答案众数是多少
  77. signed main(){
  78.   Init();  
  79.   for(int i=1,l0,r0;i<=m;++i){
  80.     int l=(read(l0)+ans-1)%n+1,r=(read(r0)+ans-1)%n+1;//加密方式
  81.     if(r<l) std::swap(l,r);
  82.     int belongL=bel[l]+1,belongR=bel[r]-1;
  83.     if(bel[l]==bel[r] || bel[l]+1==bel[r]){//两段相邻或在同一段，直接暴力.
  84.       ans=0;
  85.       for(int j=l;j<=r;++j){
  86.         cnt1[A[j]]++;
  87.         ans = cnt1[A[j]] > cnt1[0] ? B[A[j]] : ans;
  88.         ans = cnt1[A[j]] == cnt1[0] && B[A[j]] < ans ? B[A[j]] :ans;
  89.         cnt1[0] = cnt1[A[j]] > cnt1[0] ? cnt1[A[j]] : cnt1[0];
  90.       }//暴力统计，更新区间众数
  91.       printf("%d\n",ans);
  92.       for(int j=l;j<=r;++j)
  93.         cnt1[A[j]]--;
  94.       cnt1[0]=0;//还原
  95.       continue;
  96.     }    
  97.     int tmp1=mode[belongL][belongR];
  98.     int tmp2=cnt[belongL][belongR][0];//类似回滚莫队，记录原值
  99.     for(int j=l;j<=R[bel[l]];++j)
  100.       add(belongL,belongR,j);
  101.     for(int j=L[bel[r]];j<=r;++j)
  102.       add(belongL,belongR,j);//暴力添加
  103.     ans=mode[belongL][belongR];//统计答案
  104.       
  105.     mode[belongL][belongR]=tmp1;//回滚还原
  106.     cnt[belongL][belongR][0]=tmp2;
  107.     for(int j=l;j<=R[bel[l]];++j)
  108.       del(belongL,belongR,j);
  109.     for(int j=L[bel[r]];j<=r;++j)
  110.       del(belongL,belongR,j);     
  111.     printf("%d\n",ans);
  112.   }
  113.   return 0;
  114. }

题目链接：Link

题目描述：

给一个长度为 \(N\) 的序列 \(A\) ，每次询问一段区间的最大 \(rp\) 。

\(rp\) 定义：

每次从区间中任意选择一个数 \(x\) ，把 \(x\) 从序列中删除，直到区间为空。要求维护一个集合 \(S\) 。

  • 如果 \(S\) 为空，则你 \(rp\) 减 1 。
  • 如果 \(S\) 中有一个数严格大于 \(x\) ，你 \(rp\) 减 1 ，清空 \(S\) 。
  • 把 \(x\) 加入集合 \(S\) 。

询问之间互不影响，每次询问初始 \(rp=0\) 。

Solution：

发现第一次选择时，\(rp\) 一定减 1 ，之后第一条就没用了（之后的 \(S\) 不可能为空）。

考虑怎么选才能不掉 \(rp\) 。显然，只要每次选的数严格大于之前的数就行了，也就是说，选出的数应该构成一个严格上升的序列。

如果对要选择的区间从小到大排序，然后从最小的数开始选，相同的数只选一个（保证严格大于，不然会直接掉 \(rp\) ），一直选到最大的数。这样花费 1 的 \(rp\) 就把区间中每种数删除了一次。同上方法，从剩下的数种再选一次，又花了 1 的 \(rp\) 把区间中剩下的每种数删除了一次。这样每次每种数只能删掉一个，那我找找谁最抗删不就行了？

区间众数最抗删，所以要花费区间众数出现次数的 \(rp\) 删掉区间中所有数。

答案即为 T1 答案的相反数，代码不给了。

版权声明：本文为zaza-zt原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zaza-zt/p/15000395.html