浅谈分块 区间众数
前言
分块大法好（
本文直接讲例题了 qwq
P4168 [Violet]蒲公英
题目链接：P4168 [Violet]蒲公英
题意: 找到区间内编号最小的众数，强制在线
解法一
直接分块
设块长为 $len$ ，块的总数为 $t$ 个
我们先预处理出所有以块的端点为端点的区间众数和众数的出现次数
或者说就是把每个连续块组成的区间都算出编号最小众数和它的出现次数
别忘了离散化，不然MLE咯
总共有 $t^2$ 个这样的区间，每次处理 $O(n)$ ，则预处理时间复杂度为 $O(nt^2)$
暴力查询时可以在预处理过的数组基础上临时更新数组，以统计答案，再复原数组
总时间复杂度 $O(nt^2+mn/t)$
假设 $m$ 和 $n$ 数量级相同，解 $nt^2=mn/t$，$t \approx \sqrt[3]{n}$
则时间复杂度可以控制在 $O(n^{5/3})$ 内
空间复杂度比较大，$O(nt^2)$ （注：预处理所需）
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(5e4+5)
#define MAXM (int)(45)
#define pc(a) putchar(a)
template<typename T>inline void read(T &k)
{
char ch=getchar();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){pc('-');k=-k;}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,Q,len,last,t;
int id[MAXN],L[MAXN],R[MAXN],c[MAXM][MAXM][MAXN]; // c[i][j][a[k]] 表示块i~j中a[k]的出现次数
int b[MAXN],f[MAXM][MAXM][2],now[2],a[MAXN]; // f[i][j][0/1]分别记录次数和众数
void init()
{
// 预处理
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1; i<=n; i++)
a[i]=lower_bound(b+1,b+1+m,a[i])-b; // 离散化
t=pow((double)n,(double)1/3); // 块的数量
len=t?n/t:n; // 块的长度
for(int i=1; i<=t; i++)
{
L[i]=(i-1)*len+1;
R[i]=i*len;
}
if(R[t]<n)
{
L[t+1]=R[t]+1;
R[++t]=n;
}
for(int i=1; i<=t; i++)
for(int j=L[i]; j<=R[i]; j++)
id[j]=i;
for(int i=1; i<=t; i++)
for(int j=i; j<=t; j++)
{
for(int k=L[i]; k<=R[j]; k++)
++c[i][j][a[k]]; // 统计答案
for(int k=1; k<=m; k++)
{
if(c[i][j][k]>f[i][j][0]) // 更新答案
{
f[i][j][0]=c[i][j][k];
f[i][j][1]=k;
}
}
}
}
void proc(int x,int y,int k)
{
++c[x][y][k]; // 临时修改
if(c[x][y][k]>now[0]||c[x][y][k]==now[0]&&k时间<now[1])
{
now[0]=c[x][y][k]; // 更新答案
now[1]=k;
}
}
void solve(int l,int r)
{
l=(l+last-1)%n+1; // 题目要求
r=(r+last-1)%n+1;
if(l>r)swap(l,r); // 题目要求
int p=id[l],q=id[r],x=0,y=0;
if(p+1<=q-1)x=p+1,y=q-1;
memcpy(now,f[x][y],sizeof(now));
if(p==q)
{
for(int i=l; i<=r; i++)proc(x,y,a[i]); // 临时修改+更新答案
for(int i=l; i<=r; i++)--c[x][y][a[i]]; // 改回来
}else
{
for(int i=l; i<=R[p]; i++)proc(x,y,a[i]);
for(int i=L[q]; i<=r; i++)proc(x,y,a[i]);
for(int i=l; i<=R[p]; i++)--c[x][y][a[i]];
for(int i=L[q]; i<=r; i++)--c[x][y][a[i]];
}
write(last=b[now[1]]);pc('\n');
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]),b[i]=a[i];
init();
while(Q--)
{
int l,r;
read(l);read(r);
solve(l,r);
}
return 0;
}解法二
还是分块，只不过维护的东西不一样
我们发现，解法一的空间就多在了次数统计这个东西上
次数统计？不是可以二分吗？
对每个数值建个vector保存它出现的下标，出现次数就是upper_bd-lower_bd
这样我们只要预处理众数是谁就行了
暴力查询结果和众数的结果比一下就行了
别忘了离散化哦
有点时间换空间的感觉，但是还是很快
时间复杂度 $O(nt+mn/t\times \log n)$
假设 $m$ 和 $n$ 数量级相同，还是解方程，$t \approx \sqrt{n\log n}$
则时间复杂度可控制在 $O(n\sqrt{n\log n})$
空间复杂度 $O(t^2)$ ，不错
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(5e4+5)
#define MAXM (int)(888)
#define pc(a) putchar(a)
template<typename T>inline void read(T &k)
{
char ch=getchar();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){pc('-');k=-k;}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,Q,last,t,len,c[MAXN],id[MAXN];
int a[MAXN],b[MAXN],L[MAXM],R[MAXM],f[MAXM][MAXM];
vector<int> vec[MAXN];
int find(int k,int l,int r)
{
return upper_bound(vec[k].begin(),vec[k].end(),r)
-lower_bound(vec[k].begin(),vec[k].end(),l);
} // 出现次数
void proc(int k,int l,int r,int &ans,int &cnt)
{
int res=find(k,l,r);
if(res>cnt||res==cnt&&k<ans)
{
cnt=res;
ans=k;
} // 更新答案
}
void init()
{
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1; i<=n; i++)
{
a[i]=lower_bound(b+1,b+1+m,a[i])-b;
vec[a[i]].push_back(i); // 记录下标
}
t=sqrt(log(n)/log(2)*n);
len=t?n/t:n;
for(int i=1; i<=t; i++)
{
L[i]=(i-1)*len+1;
R[i]=i*len;
}
if(R[t]<n)
{
L[t+1]=R[t]+1;
R[++t]=n;
}
for(int i=1; i<=t; i++)
for(int j=L[i]; j<=R[i]; j++)
id[j]=i;
for(int i=1; i<=t; i++)
{
memset(c,0,sizeof(c)); // 统计次数
int cnt=0,ans=0;
for(int j=L[i]; j<=n; j++)
{
++c[a[j]];
if(c[a[j]]>cnt||c[a[j]]==cnt&&a[j]<ans)
{
cnt=c[a[j]];
ans=a[j];
}
f[i][id[j]]=ans; // 众数
}
}
}
void solve(int l,int r)
{
l=(l+last-1)%n+1;
r=(r+last-1)%n+1;
if(l>r)swap(l,r);
int p=id[l],q=id[r],x=0,y=0,ans=0,cnt=0;
if(p+1<=q-1)x=p+1,y=q-1;
if(p==q)
{
for(int i=l; i<=r; i++)
proc(a[i],l,r,ans,cnt);
}else
{
for(int i=l; i<=R[p]; i++)proc(a[i],l,r,ans,cnt);
for(int i=L[q]; i<=r; i++)proc(a[i],l,r,ans,cnt);
}
if(f[x][y])proc(f[x][y],l,r,ans,cnt);
write(last=b[ans]);pc('\n');
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]),b[i]=a[i];
init();
while(Q--)
{
int l,r;
read(l);read(r);
solve(l,r);
}
return 0;
}然后我们就想到
如果只需要知道众数的出现次数，有没有什么好的办法呢？
[Ynoi2019 模拟赛] Yuno loves sqrt technology III
题目链接：[Ynoi2019 模拟赛] Yuno loves sqrt technology III
题意：区间众数出现次数，强制在线
类似于上一题的解法二，这题 $t=\sqrt{n}$ 即可
不同的是，我们要预处理出连续块的众数出现次数
然后还是每个数值建一个vector，统计出现的下标
再记录每个存的下标在vector中的下标 $ax_i$
显然非暴力查询的区域，答案 $res=f[x][y]$
因为边界数最多对答案有 $2\sqrt{n}$ 的贡献
所以暴力查询时，对于每个左侧元素 $k$ ，我们只要找到 $k$ 的vector中 $ax_k+res$ 的位置的元素，看它是不是小于 $r$ ，如果小于 $r$ ，说明它一定更接近最终答案且在该区间内，更新 $res$
对于每个右侧元素 $k$ ，我们只要找到 $k$ 的vector中 $ax_k-res$ 的位置的元素，看它是不是大于 $l$ ，原理同上
最终答案即为 $res$
时间复杂度 $O((n+m)\sqrt{n})$
空间复杂度 $O(n)$
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(5e5+5)
#define MAXM (int)(888)
#define pc(a) putchar(a)
template<typename T>inline void read(T &k)
{
char ch=getchar();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){pc('-');k=-k;}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,Q,last,t,len,c[MAXN],id[MAXN],cnt[MAXN];
int a[MAXN],b[MAXN],L[MAXM],R[MAXM],f[MAXM][MAXM],ax[MAXN];
vector<int> vec[MAXN];
void init()
{
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1; i<=n; i++)
{
a[i]=lower_bound(b+1,b+1+m,a[i])-b; // 离散化
vec[a[i]].push_back(i); // 下标
ax[i]=vec[a[i]].size()-1; // 每个下标在vector中的下标
}
t=sqrt(n);
len=t?n/t:n;
for(int i=1; i<=t; i++)
{
L[i]=(i-1)*len+1;
R[i]=i*len;
}
if(R[t]<n)
{
L[t+1]=R[t]+1;
R[++t]=n;
}
for(int i=1; i<=t; i++)
for(int j=L[i]; j<=R[i]; j++)
id[j]=i;
for(int i=1; i<=t; i++)
{
memset(c,0,sizeof(c));
for(int j=i; j<=t; j++)
{
f[i][j]=f[i][j-1];
for(int k=L[j]; k<=R[j]; k++)
f[i][j]=max(++c[a[k]],f[i][j]);
// 统计次数即可（它又不要知道众数是谁咯 qwq）
}
}
}
void solve(int l,int r)
{
l^=last;r^=last; // 题目要求
if(l>r)swap(l,r);
int p=id[l],q=id[r],x=0,y=0,res=0;
if(p+1<=q-1)x=p+1,y=q-1;
if(p==q)
{
for(int i=l; i<=r; i++)
cnt[a[i]]=0;
for(int i=l; i<=r; i++)
res=max(++cnt[a[i]],res);
}else
{
res=f[x][y];
for(int i=l; i<=R[p]; i++)
{
int it=ax[i]+res;
while(it<vec[a[i]].size()&&vec[a[i]][it]<=r)
{++res;++it;} // 暴力扩展+更新答案
}
for(int i=L[q]; i<=r; i++)
{
int it=ax[i]-res;
while(it>=0&&vec[a[i]][it]>=l)
{++res;--it;}
}
}
write(last=res);pc('\n');
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]),b[i]=a[i];
init();
while(Q--)
{
int l,r;
read(l);read(r);
solve(l,r);
}
return 0;
}总结
本文简单讲了下区间众数的分块解法
