CF1446D2 Solution

link

首先，最终答案区间中的众数一定包括整个序列的众数 \(K\)。

证明：设这个区间中众数出现次数为 \(cnt\)。

如果上述不成立，由于 \(K\) 在这个区间中出现次数小于 \(cnt\)，我们将区间向两边延申，

\(K\) 的出现次数应当不断增加直到等于区间的众数出现次数。这样子就找到了更长的区间。因此结论成立。

那么现在要求的就是，求一个最长的区间，满足 \(K\) 的出现次数等于其众数出现次数。

我们对这个出现次数根号分治。如果出现次数大于根号，这样的众数只有根号种。

枚举每一个这样的数 \(x\)，求一下最长区间使得包含的 \(x,K\) 个数相同。

这里可能会有不合法的区间。但是没关系，不合法算出来的答案一定不优于最终答案。

这个问题容易解决，可以做到单次线性。这部分复杂度就是线性根号。

如果出现次数小于根号，我们枚举这个出现次数 \(c\)。

然后求，最长的区间满足众数出现次数为 \(c\) 且众数至少有两个。

考虑双指针，右端点右移时左端点右移直到众数出现次数 \(<c\) 或者只剩一个众数了。

每次的移动类似区间众数的莫队做法。具体地，维护每个数出现次数以及每个出现次数的出现次数。容易转移。

这部分也是线性根号的。最终复杂度 \(\mathcal O(n\sqrt n)\)。

---待补代码，没时间写了---