给定长 的序列 。
输出最长的满足不同的众数(出现次数最多的数)至少有两个的区间的长度。
D1:,;
D2:,;
现特判掉整个序列不同众数个数 的情况。
设 为整个序列的众数,有个结论:
一定是答案区间的其中一个众数。
证明考虑反证,若 不是答案区间的众数,因为 是序列中最多的数,所以一定可以向左向右拓展答案区间使得 是答案区间的众数,这样一定不劣因为原来的众数还是众数。
那么 D1 就可以直接枚举答案区间的另一个众数 然后 找到最长的满足 和 出现次数相等的区间,总时间复杂度 。
对于 D2,注意到是颜色题,所以考虑根号分治。
- 对于出现次数 的数,直接用 D1 的做法,这部分总时间复杂度 ;
- 对于出现次数 的数,直接枚举众数的出现次数然后双指针找到最长的合法区间,这部分总时间复杂度 ;
总时间复杂度 ,代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int S=200005,B=450;
int n,a[S];
int cnt[S];
int mnp[S*2],b[S];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) cnt[a[i]]++;
int mx=0,val;
for(int i=1;i<=n;i++) if(cnt[i]>mx) mx=cnt[i],val=i;
for(int i=1;i<=n;i++) if(i!=val&&cnt[i]==mx) return printf("%d\n",n),0;
int ans=0;
for(int i=1;i<=n;i++)
{
if(i==val) continue;
if(cnt[i]>B)
{
for(int j=0;j<=n+n;j++) mnp[j]=0;
int cnt=0;
for(int j=1;j<=n;j++)
{
if(a[j]==i) cnt--;
if(a[j]==val) cnt++;
if(cnt==0||mnp[n+cnt]!=0) ans=max(ans,j-mnp[n+cnt]);
else mnp[n+cnt]=j;
}
}
}
for(int i=1;i<=B;i++)
{
for(int j=1;j<=n;j++) b[j]=0;
int l=1,cnt=0;
for(int r=1;r<=n;r++)
{
cnt+=++b[a[r]]==i;
while(l<=r&&b[a[r]]>i)
{
cnt-=b[a[l++]]--==i;
}
if(cnt>=2) ans=max(ans,r-l+1);
}
}
printf("%d\n",ans);
return 0;
}