有一个显然的贪心，选了一个区间 \([l,r]\) ,贡献为这个区间的众数加上区间外的众数。
考虑根号分治，阈值为 \(B\) 。我们称出现次数 \(>B\) 的数称为大数，反之成为小数。答案有需要分 \(4\) 类讨论： \([l,r]\) 内是大数/小数，区间外是大数/小数
比较简单的是 \([l,r]\) 内是大数/小数，区间外是大数。
我们发现大数的种类只有 \(\frac{n}{B}\) 个，所以我们预处理出 \(sum_{i,j}\) 表示前缀 \(i\) 数字 \(j\) 出现了多少次？这个部分容易做到 \(O(n \sqrt n)\) 。
接下来我们枚举一种颜色，然后对于这个元素从左到右数的第 \(i\) 个出现位置假设我们的区间 \([l,r]\) 以其为右端点，那么对于一个左端点 \(j\) (这个元素第 \(j\) 个出现的位置)产生的贡献就是 \((i-j+1)+(sum_{n,w}-sum_{i,w})+sum_{j-1,w}\)
推推柿子：
\[\max_{j<i}(i-j+1)+(sum_{n,w}-sum_{i,w})+sum_{j-1,w} \]\[(i-sum_{i,w}+sum_{n,w}+1)-(\min_{j<i}sum_{j-1,w}-j) \]后面的 \(\min\) 可以预处理啊，所以这部分可以做 \(O(\frac{n^2}{B})\) 。
十分困难的是 \([l,r]\) 内是小数，区间外是小数。
因为区间内是小数，所以这样的区间只有 \(O(nB)\) 个，考虑 \(O(1)\) 求区间外的小数，优势在于小数的数量 \(\leqslant B\) 。
记录 \(f_{i,j}\) 表示左端点 \(i\) 要是需要出现 \(j\) 个元素，最靠右的右端点是多少？这个东西比较容易预处理，时间 \(O(nB)\) 。那么我们对于枚举的一个区间 \([l,r]\) ，我们找到 \(f_{l-1,i}>r\) 并且 \(i\) 尽量大。因为 \(f\) 数组有单调性，所以二分这个 \(i\) 。可以做到 \(O(nB \log B)\) 。
看起来比较简单，但是没有那么好想。我想了半小时（可能是我菜）。
中规中矩的是 \([l,r]\) 内是大数，区间外是小数。
下文中的 \(f\) 数组与上述定义一致。
标签：大数,sum,Luogu8330,报告,解题,端点,区间,外是,小数 From： https://www.cnblogs.com/Diavolo/p/17809826.html