题意简述
给定一个长度为 (n) 的数列 ({a_i})，满足 (1le a_ile n)。
求一个最长的子区间，使得这个子区间内出现次数最多的数不止一个。
数据范围：(1le nle 2 imes10^5)。
对于简单版有 (1le a_ile 100)。
Solution
看上去没办法用数据结构强行维护，考虑做一些转化。
考虑长度为 (i) 的前缀，设这个前缀存在唯一出现次数最多的数为 (x)，令左端点 (j) 初始为 (1)。
在左端点 (j) 不断加 (1) 的过程中，维护 ([j,i]) 内每种数的出现次数，一旦当前存在一个 (y e x) 满足 (y) 和 (x) 出现次数相等，就停止扫描，这时候可以用 (i-j+1) 更新答案。
设 (s_{i,x,y}=sum_{j=1}^i[a_j=x]-sum_{j=1}^i[a_j=y])，则对于右端点 (i)，出现次数最多的数为 (x)，其最小合法左端点为：
即对于每种不为 (x) 的数 (y) 都考虑其第一次出现次数相等的位置取个最小值。
于是可以枚举 (x) 和 (y)，注意到我们一定有 (a_{ ext{minimum }j ext{ satisfying }s_{j,x,y}=s_{i,x,y}}=x)，故可以枚举所有 (a_i=x) 的位置 (i) 和所有满足 ([1,i]) 中出现次数最多的数为 (x) 的位置 (i) 来求出 ( ext{minimum }j ext{ satisfying }s_{j,x,y}=s_{i,x,y})，期间需要对每种 (s_{i,x,y}) 的出现位置记录一个数组，并且需要一些特殊技巧来达到 (O(n)) 的空间。
这样可以过 Easy。对于 Hard，取 (S=lfloorsqrt n floor)，把数分成出现次数 (le S) 和 (>S) 两类，用上面的方法可以 (O(nS)) 求出所有满足最大出现次数 (>S) 的区间长度最大值。
对于最大出现次数 (le S) 的区间，不难发现区间右端点和最大出现次数确定了之后，只需考虑最小的左端点，故这一部分外围枚举 (1le jle S) 表示最大出现次数，然后右端点 (i) 从小到大用 two-pointers 维护最小左端点即可，这一部分复杂度也是 (O(nS))，总复杂度 (O(nsqrt n))。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}
const int N = 2e5 + 5;
int n, a[N], ans, cnt[N], ty[N], c[N], z[N], o[N], s[N], ToT, vis[N], fis[N],
S, b[N], id[N], tot;
std::vector<int> ot[N], occ[N];
void inc(int c, int i, int &cur1, int &cur2, int delta)
{
if (cnt[c] == i) cur1--; if (cnt[c] > i) cur2--;
cnt[c] += delta;
if (cnt[c] == i) cur1++; if (cnt[c] > i) cur2++;
}
int main()
{
int cur = 0, x;
read(n); S = sqrt(n);
for (int i = 1; i <= n; i++) read(a[i]), b[a[i]]++;
for (int i = 1; i <= n; i++) if (b[i] > S) id[i] = ++tot;
for (int i = 1; i <= n; i++)
{
if ((++cnt[a[i]]) > cur) cur = cnt[a[i]], x = a[i];
else if (cnt[a[i]] == cur) x = -1;
ty[i] = x; c[i] = cur; o[i] = cnt[a[i]];
if (x == -1) ans = i;
if (id[a[i]]) ot[id[a[i]]].push_back(-i);
if (x > 0 && id[x]) ot[id[x]].push_back(i);
}
for (int i = 1; i <= n; i++) z[i] = n + 1;
for (int T = 1; T <= tot; T++)
{
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + (id[a[i]] == T);
for (int D = 1; D <= tot; D++) if (D != T)
{
ToT++;
for (int i = 0; i < ot[D].size(); i++)
if (ot[D][i] < 0)
{
int tmp = o[-ot[D][i]] - s[-ot[D][i]];
if (tmp >= 0 && vis[tmp] < ToT)
vis[tmp] = ToT, fis[tmp] = -ot[D][i];
}
else
{
int tmp = c[ot[D][i]] - s[ot[D][i]];
if (vis[tmp] == ToT)
z[ot[D][i]] = Min(z[ot[D][i]], fis[tmp]);
}
}
}
for (int i = 1; i <= n; i++) ans = Max(ans, i - z[i]);
for (int T = 1; T <= S; T++)
{
memset(cnt, 0, sizeof(cnt));
for (int i = 1, j = 1, cur1 = 0, cur2 = 0; i <= n; i++)
{
inc(a[i], T, cur1, cur2, 1);
while (cur2) inc(a[j], T, cur1, cur2, -1), j++;
if (cur1 > 1) ans = Max(ans, i - j + 1);
}
}
return std::cout << ans << std::endl, 0;
}