题解 CF1446D2 【Frequency Problem (Hard Version)】

tommymio

2020-11-19 15:01:27

Solution

结论题。一个很常用的结论,众数与子区间的关系。 可以发现,答案子段的众数集合一定包含整个序列的众数 $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; } ```