CF1446D1&2 Frequency Problem 做题记录

给定长 $n$ 的序列 $a_{[1,n]}$。

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

D1：$1\le n\le 2\times 10^5$，$1\le a_i\le \min(100,n)$；

D2：$1\le n\le 2\times 10^5$，$1\le a_i\le n$；

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

设 $X$ 为整个序列的众数，有个结论：

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

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

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

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

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

总时间复杂度 $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;
}