题解 CF1446D2 【Frequency Problem (Hard Version)】
tommymio
2020-11-19 15:01:27
结论题。一个很常用的结论,众数与子区间的关系。
可以发现,答案子段的众数集合一定包含整个序列的众数 $X$。反证法证明:如果不包含这个众数 $X$,则说明子段众数出现次数在这个子段中,大于序列众数 $X$。因为众数 $X$ 是序列中出现最多的数,所以我们可以向左 $/$ 向右拓展这个子段,令众数的 $X$ 的出现次数不小于子段众数出现次数,这样做答案显然更优。
问题即转化为,找一个子段令其中 $X$ 的出现次数与其中另一个数出现次数相同,并且令这个子段长度最大。考虑 $\text{Easy Version}$ 的做法:枚举另一个数 $Y$,找一段 $X$ 出现次数与 $Y$ 出现次数相同的子段,时间复杂度为 $O(nV)$,其中 $V$ 为值域。
怎么优化呢?像这类与值域相关的问题,我们一般会想到根号分治。考虑那些出现次数 $> \sqrt n$ 的数,这些数的种类 $< \sqrt n$,所以可以使用 $\text{Easy Version}$ 的做法,时间复杂度为 $O(n\sqrt n)$。再考虑那些出现次数 $\leq \sqrt n$ 的数,我们枚举区间内一个数的最大出现次数,使用 $\text{two-pointer}$ 判断是否有至少两个不同的达到这个最大出现次数即可,时间复杂度为 $O(n\sqrt n)$。所以总时间复杂度就为 $O(n\sqrt n)$。
$\text{two-pointer}$ 的部分有些小细节,可以参考代码理解一下。
```cpp
#include<cstdio>
#include<cmath>
const int N=200000;
int t[N<<1|1],tmp[N<<1|1],a[N];
inline int read() {
register int x=0,f=1;register char s=getchar();
while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
inline int max(const int &x,const int &y) {return x>y? x:y;}
int main() {
int n=read(),bound=sqrt(n);
for(register int i=1;i<=n;++i) {a[i]=read(); ++t[a[i]];}
int mode=0,mx=0;
for(register int i=1;i<=n;++i) if(t[mode]<t[i]) mode=i;
for(register int x=1;x<=n;++x) {
if(t[x]>bound) {
if(x==mode) continue;
int cnt=0;tmp[N]=0;
for(register int i=1;i<=n;++i) {
if(a[i]==mode) {++cnt;}
else if(a[i]==x) {--cnt;}
if(tmp[cnt+N]||cnt==0) {mx=max(mx,i-tmp[cnt+N]);}
else {tmp[cnt+N]=i;}
}
cnt=0;
for(register int i=1;i<=n;++i) {
if(a[i]==mode) {++cnt;}
else if(a[i]==x) {--cnt;}
tmp[cnt+N]=0;
}
}
}
for(register int x=1;x<=bound;++x) {
int L=1,cnt=0;
for(register int i=1;i<=n;++i) tmp[i]=0;
for(register int i=1;i<=n;++i) {
++tmp[a[i]];
if(tmp[a[i]]==x) ++cnt;
while(L<=i&&tmp[a[i]]>x) {
if(tmp[a[L]]==x) --cnt;
--tmp[a[L]];
++L;
}
if(cnt>=2) mx=max(mx,i-L+1);
}
}
printf("%d\n",mx);
return 0;
}
```