CF1446D1&2 Frequency Problem 做题记录

给定长 nn 的序列 a[1,n]a_{[1,n]}

输出最长的满足不同的众数(出现次数最多的数)至少有两个的区间的长度。

D1:1n2×1051\le n\le 2\times 10^51aimin(100,n)1\le a_i\le \min(100,n)

D2:1n2×1051\le n\le 2\times 10^51ain1\le a_i\le n

现特判掉整个序列不同众数个数 >1>1 的情况。

XX 为整个序列的众数,有个结论:

XX 一定是答案区间的其中一个众数。

证明考虑反证,若 XX 不是答案区间的众数,因为 XX 是序列中最多的数,所以一定可以向左向右拓展答案区间使得 XX 是答案区间的众数,这样一定不劣因为原来的众数还是众数。

那么 D1 就可以直接枚举答案区间的另一个众数 YY 然后 O(n)O(n) 找到最长的满足 XXYY 出现次数相等的区间,总时间复杂度 O(nV)O(nV)

对于 D2,注意到是颜色题,所以考虑根号分治。

  • 对于出现次数 >n> \sqrt n 的数,直接用 D1 的做法,这部分总时间复杂度 O(nn)O(n\sqrt n)
  • 对于出现次数 n\le \sqrt n 的数,直接枚举众数的出现次数然后双指针找到最长的合法区间,这部分总时间复杂度 O(nn)O(n\sqrt n)

总时间复杂度 O(nn)O(n\sqrt n),代码如下:

#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;
}