找不到头图了就随机传了一张。 其实一直很好奇日富美的距离感（以及佩洛洛的魅力）。
转题意，要你求一段区间，使得区间内的众数加扣掉区间的原序列的众数和最大。
如果确定了要选的区间内的数和区间外的数，那么找这一段区间就是一个最大子段和问题了。
怎么来的？
假设你令区间外的数为
怎么用这个性质。看题解根号分治。
令
你发现在一个数
具体地，先讨论这个数
现在还剩下一种情况，区间外
我会暴力，111。
扫描线，设新增
cpp
#include<bits/stdc++.h>
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
#define pb push_back
#define ins insert
using namespace std;
const int N=5e5+10,mod=998244353;
int n,cnt,B,ans;
int a[N];
int lsh[N];
int num[N];
bitset<N>lgr;
vector<int>pos[N],answer;
int sum[N];
int S[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
// init
memset(sum,0,sizeof sum);
memset(S,0,sizeof S);
lgr.reset();
rep(i,1,500005)pos[i].clear();
answer.clear();
memset(num,0,sizeof num);
memset(lsh,0,sizeof lsh);
ans=0;cnt=0;
// input
cin>>n;B=sqrt(n);rep(i,1,n)cin>>a[i],lsh[++cnt]=a[i];
sort(lsh+1,lsh+cnt+1);cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
rep(i,1,n){
a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
++num[a[i]];
lgr[a[i]]=(num[a[i]]>B);
pos[a[i]].pb(i);
}
// r1
for(int x=lgr._Find_first();x!=lgr.size();x=lgr._Find_next(x)){
// x is outside
rep(i,1,n)sum[i]=sum[i-1]-(a[i]==x);
rep(y,1,cnt){
reg int tmp=0,pre=0,tot=0;
for(auto p:pos[y])pre=min(pre,sum[p-1]+tot++),tmp=max(tmp,sum[p]-pre+tot);
// update
if(tmp+num[x]==ans)answer.pb(x);
else if(ans<tmp+num[x])answer.clear(),ans=tmp+num[x],answer.pb(x);
}
// x is inside
rep(i,1,n)sum[i]=sum[i-1]+(a[i]==x);
rep(y,1,cnt){
reg int tmp=0,pre=0,tot=0;
for(auto p:pos[y])tmp=max(tmp,sum[p]-tot-pre),pre=min(pre,sum[p]-++tot);
if(tmp+num[y]==ans)answer.pb(y);
else if(ans<tmp+num[y])answer.clear(),ans=tmp+num[y],answer.pb(y);
}
}
// r2
rep(i,1,cnt)pos[i].ins(pos[i].begin(),0);
rep(r,1,n){
if(num[a[r]]<=B){
reg int p=lower_bound(pos[a[r]].begin(),pos[a[r]].end(),r)-pos[a[r]].begin(),g=p-1;
for (auto l:pos[a[r]])if(l++<r){
int tmp=num[a[r]]+S[l]-g--;
if(tmp==ans)answer.pb(a[r]);
else if(ans<tmp)answer.clear(),ans=tmp,answer.pb(a[r]);
}
rep(i,0,p){
int k=p-i+1,f=pos[a[r]][i];
while(f&&S[f]<k)S[f--]=k;
}
}
}
rep(i,1,cnt){
int g=pos[i].size()-1;
for (auto l:pos[i]) {
int tmp=num[i]+S[++l]-g--;
if(tmp==ans)answer.pb(i);
else if(ans<tmp)answer.clear(),ans=tmp,answer.pb(i);
}
}
// output
cout<<ans<<'\n';sort(answer.begin(),answer.end());answer.resize(unique(answer.begin(),answer.end())-answer.begin());for(auto it:answer)cout<<lsh[it]<<'\n';
}
return 0;
}