考虑求出全局的众数 \(A\)。
那么有一个结论，就是答案区间的众数中绝对有 \(A\)。
考虑反证法，如果没有 \(A\)，\(A\) 在序列中出现的个数一定 \(\ge\) 区间内众数的出现个数，所以可以一直往外扩展直到 \(A\) 出现的个数与区间内非 \(A\) 众数的个数持平，这样肯定更优。
于是可以考虑钦定区间的另一个众数为 \(B\)。
那么把 \(a_i = A\) 的看作 \(1\)，\(= B\) 的看作 \(-1\)，其他的看作 \(= 0\)。
那么 \(\sum = 0\) 的区间就说明 \(A, B\) 个数相同，便可以统计进答案。
可以做出前缀和维护每种前缀和最先出现的位置得到答案。
时间复杂度 \(O(nV)\)，\(\text{Easy Version}\) 的做法。
因为每种数出现个数之和 \(= n\)，考虑根号分治。
对于出现次数 \(> \sqrt{n}\) 的做这种操作。
对于出现次数 \(\le \sqrt{n}\) 的，考虑枚举众数的出现个数 \(c\)。
考虑双指针维护，如果 \(r - 1\) 扩展到 \(r\) 后 \([l, r]\) 内 \(a_r\) 的出现次数 \(> c\)，不符合条件，就考虑一直删掉 \(l\) 位置的数直到 \(a_r\) 的出现次数 \(= c\)。
如果对于 \([l, r]\) 满足有至少 \(2\) 种数出现次数是 \(c\)，就是一个合法的区间。
时间复杂度 \(O(n\sqrt{n})\)。
代码
#include<bits/stdc++.h>
const int maxn = 4e5 + 10;
int a[maxn];
int cnt[maxn], L[maxn];
int main() {
int n; scanf("%d", &n);
int len = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) cnt[a[i]]++;
int A = 1;
for (int i = 1; i <= n; i++) cnt[i] > cnt[A] && (A = i);
int ans = 0;
memset(L, -1, sizeof(L));
for (int B = 1; B <= n; B++) {
if (A == B || cnt[B] <= len) continue;
int tot = 0; L[n] = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == A) tot++;
else if (a[i] == B) tot--;
if (~ L[tot + n]) ans = std::max(ans, i - L[tot + n]);
else L[tot + n] = i;
}
tot = 0, L[n] = -1;
for (int i = 1; i <= n; i++) {
if (a[i] == A) tot++;
else if (a[i] == B) tot--;
L[tot + n] = -1;
}
}
for (int mx = 1; mx <= len; mx++) {
memset(cnt, 0, sizeof(cnt));
int tot = 0;
for (int r = 1, l = 1; r <= n; r++) {
if (cnt[a[r]] == mx) {
while (a[l] != a[r]) tot -= (cnt[a[l]]-- == mx), l++;
l++;
} else tot += (++cnt[a[r]] == mx);
tot >= 2 && (ans = std::max(ans, r - l + 1));
}
}
printf("%d\n", ans);
return 0;
}