Codeforces

分析

先判掉只有一种数的情况，答案显然为 $0$。

再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。

那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。

这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原来最多的出现次数的时刻。

考虑枚举另外一个出现次数和 $x$ 相同的数 $y$。我们把 $x$ 看成 $1$、$y$ 看成 $-1$，相当于求最长的和为 $0$ 的一段，记录每个前缀和出现的最前的位置即可。这样子是 $\mathcal{O}(n^2)$ 的。

还可以考虑枚举最终 $x$ 的出现次数 $c$，然后枚举右端点，双指针维护最左的满足所有数在 $[l,r]$ 内出现次数 $\leq c$ 的 $l$，并更新答案。这样子也是 $\mathcal{O}(n^2)$ 的。

考虑根号分治。对于出现次数 $>B$ 的 $y$，我们使用第一种做法，复杂度 $\mathcal{O}(\frac{n^2}{B})$；然后我们对 $\leq B$ 的出现次数使用第二种做法，复杂度 $\mathcal{O}(nB)$。取 $B=\sqrt{n}$，总时间复杂度 $\mathcal{O}(n\sqrt{n})$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,B=447;

int n,a[N],o[N],pre[N<<1],c[N];

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) ++o[a[i]];
    int mx=0,mx2=0;
    for (int i=1;i<=n;++i) {
        if (o[i]>o[mx]) mx2=mx,mx=i;
        else if (o[i]>o[mx2]) mx2=i;
    }
    if (!mx2) { puts("0"); return 0; }
    if (o[mx]==o[mx2]) { printf("%d\n",n); return 0; }
    int ans=0;
    for (int i=1;i<=n;++i) {
        if (i==mx||o[i]<=B) continue;
        for (int j=0;j<=n<<1;++j) pre[j]=-1;
        pre[n]=0;
        for (int j=1,s=0;j<=n;++j) {
            if (a[j]==mx) ++s;
            if (a[j]==i) --s;
            if (~pre[s+n]) ans=max(ans,j-pre[s+n]);
            else pre[s+n]=j;
        }
    }
    for (int i=1;i<=B;++i) {
        for (int j=1;j<=n;++j) o[j]=c[j]=0;
        for (int r=1,l=1;r<=n;++r) {
            --c[o[a[r]]],++o[a[r]],++c[o[a[r]]];
            while (l<r&&o[a[r]]>i) --c[o[a[l]]],--o[a[l]],++c[o[a[l]]],++l;
            if (c[i]>=2) ans=max(ans,r-l+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}