众数 题解
Eraine
·
2024-08-12 21:31:56
·
题解
来源：浙江省选 2022
编号：P8330
tag：根号分治
难度：紫
没怎么理解题解区大佬的题解，若有重复请见谅。
考虑最终答案的形态。x 为最终众数的答案必然为 x\dots x,x-k\dots x-k,x\dots x 。前后两段 x 不一定要同时出现，但是至少要出现一段（不然就变成一些数变成左右段序列没有出现过的数就不会更优，容易证明一定有比完全更优的解）。
wjz 学长说的很有道理，出现次数 一般和 根号分治 挂钩。所以我们考虑对用一种颜色出现次数进行根号分治。设阈值为 B 。
当 cnt_p\gt B 时，把这些颜色单独拎出来做。具体地，处理颜色 p 的前后缀出现次数，然后对于每一种其他颜色 i ，处理出类似 i\dots i,p\dots p,i\dots i 和 p\dots p,i\dots i,p\dots p 形态的的答案并分别对 ans_i,ans_p 进行贡献。这很好处理，对于 i\dots i,p\dots p,i\dots i ，处理出每个 i 作为左段右端点和右端左端点对答案产生的影响 sum_i-sum_p 。处理前后缀 \max 很容易做到线性。故这部分总时间复杂度为 \Theta(\frac{n^2}{B}) 。
当 cnt_p\le B 时，考虑到此时只剩左右段和中间段出现次数均 \le B 的情况。固定中间段的右端点发现最优中间段仅有 B 种，即其他颜色分别出现 1\sim B 次。接下来只要考虑如何统计颜色 p 作为左右段颜色的贡献和颜色 p 作为中间段颜色的贡献。右端点扫描线，f_i 表示当前节点作为右端点，其他颜色作为中间段出现 i 次的最大左端点，每遍历到一个颜色就对这个大小为 B 的数组进行遍历更新。考虑 p 作为左右段颜色产生贡献，只需枚举 p 位置集合元素作为左端点时最大的 i 满足 f_i\ge L 。由于 f_i 单调递减，所以在倒序遍历颜色 p 集合的同时放一个指针在 f 数组上跑，类似双指针的思想。可以发现每个元素最多贡献 \Theta(\max(B,cnt_p)) 。故总时间复杂度为 \Theta(nB) 。
注意有可能区间不恰好包含在两个同颜色元素之间，所以单独前后缀处理一下即可。
当 B 取 \sqrt{n} 有最优复杂度。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int K=455;
const int inf=1e9;
int n,a[N],num,B;
int cnt[N];
int m,tmp[N];
vector<int>lnk[N];
int ans[N];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
lnk[i].clear();
ans[i]=0;
cnt[i]=0;
}
m=n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
tmp[i]=a[i];
}
sort(tmp+1,tmp+m+1);
m=unique(tmp+1,tmp+m+1)-tmp-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(tmp+1,tmp+m+1,a[i])-tmp;
lnk[a[i]].push_back(i);
++cnt[a[i]];
}
B=sqrt(n*1.0);
}
int f[N],g[N],F[N],G[N];
void big(int p){
for(int i=0;i<=n+1;i++){
f[i]=g[i]=0;
}
for(auto x:lnk[p]){
++f[x];
++g[x];
}
for(int i=1;i<=n;i++){
f[i]=f[i]+f[i-1];
}
for(int i=n;i;i--){
g[i]=g[i]+g[i+1];
}
int val=cnt[p];
for(int i=1;i<=m;i++){
if(i==p){
continue;
}
int k=cnt[i];
int res=-inf;
F[0]=G[k+1]=0;
for(int j=0;j<k;j++){
F[j+1]=max(F[j],(j+1)-f[lnk[i][j]]);
res=max(res,F[j+1]+val);
}
for(int j=k-1;~j;j--){
G[j+1]=max(G[j+2],(k-(j+1)+1)-g[lnk[i][j]]);
res=max(res,G[j+1]+val);
}
for(int j=1;j<=k;j++){
res=max(res,F[j]+G[j]+val);
}
ans[i]=max(ans[i],res);
res=-inf;
F[0]=G[k+1]=0;
for(int j=0;j<k;j++){
F[j+1]=max(F[j],f[lnk[i][j]]-j);
res=max(res,F[j+1]+k);
}
for(int j=k-1;~j;j--){
G[j+1]=max(G[j+2],g[lnk[i][j]]-(k-(j+1)));
res=max(res,G[j+1]+k);
}
for(int j=1;j<=k;j++){
res=max(res,F[j]+G[j]+k);
}
ans[p]=max(ans[p],res);
}
}
int h[K];
void small(){
for(int i=1;i<=B;i++){
h[i]=0;
}
for(int i=1;i<=n;i++){
if(cnt[a[i]]>B){
continue;
}
int k=cnt[a[i]],sz=k,p=0;
for(int j=k-1;~j;j--){
if(lnk[a[i]][j]>=i){
continue;
}
while(p+1<=B&&h[p+1]>lnk[a[i]][j]){
++p;
}
ans[a[i]]=max(ans[a[i]],sz+p);
--sz;
}
sz=0;
for(int j=k-1;~j;j--){
if(lnk[a[i]][j]>i){
continue;
}
++sz;
h[sz]=max(h[sz],lnk[a[i]][j]);
}
}
}
int buc[N],id[N],pre[N],suf[N];
void spc(){
for(int i=1;i<=n;i++){
buc[i]=0;
}
for(int i=1;i<=n;i++){
pre[i]=id[i]=++buc[a[i]];
suf[i]=cnt[a[i]]-buc[a[i]]+1;
}
pre[0]=suf[n+1]=0;
for(int i=1;i<=n;i++){
pre[i]=max(pre[i],pre[i-1]);
}
for(int i=n;i;i--){
suf[i]=max(suf[i],suf[i+1]);
}
for(int i=1;i<=n;i++){
ans[a[i]]=max(ans[a[i]],id[i]+suf[i+1]);
ans[a[i]]=max(ans[a[i]],(cnt[a[i]]-id[i]+1)+pre[i-1]);
}
}
void print(){
int val=0;
for(int i=1;i<=m;i++){
val=max(val,ans[i]);
}
printf("%d\n",val);
for(int i=1;i<=m;i++){
if(ans[i]==val){
printf("%d\n",tmp[i]);
}
}
}
void solve(){
init();
for(int i=1;i<=m;i++){
if(cnt[i]>B){
big(i);
}
}
small();
spc();
print();
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
```
若有疑问或错误请指出，虚心接受您的意见。