题解

思路

设选择的区间内，某个原值 $x\ne c$ 通过加上 $k=c-x$ 变成 $c$。区间内每个等于 $x$ 的位置贡献 $+1$，而原本等于 $c$ 的位置会被改走，贡献 $-1$；其他位置贡献 $0$。

因此答案等于原序列中 $c$ 的个数，加上对某个 $x\ne c$ 的 $+1/-1/0$ 序列的最大子段和。

做法

子任务 1：枚举目标值与区间

$n\le20$ 时，枚举序列中出现的 $x\ne c$ 以及所有 $[l,r]$，直接计算净增量。

子任务 2：逐值运行 Kadane

$n\le2000$ 时，对每个不同的 $x\ne c$ 扫描整个数组：$a_i=x$ 时权值为 $1$，$a_i=c$ 时为 $-1$，否则为 $0$。用 Kadane 算法求最大子段和。复杂度为 $O(nV)$，其中 $V$ 是不同值数量，最坏为 $O(n^2)$。

子任务 3：按值维护线性 DP

从左向右扫描。令 countC 为已经遇到的 $c$ 数量。对每个值 $x\ne c$，维护以它最近一次出现为右端点的最大净增量 best[x]，以及它上次出现时的 countC。

再次遇到 $x$ 时，若延续原区间，需要减去两次出现之间新增的 $c$ 数量，再加上本次的 $1$；也可以从当前位置重新开始：

所有值的最大 best 就是最多新增数量。

正确性证明

引理 1

固定 $x\ne c$ 后，对区间加上 $c-x$ 的净增量等于区间内 $x$ 的个数减去 $c$ 的个数。

证明：区间内的 $x$ 全部变成 $c$，各新增一个；原有 $c$ 因加上非零数而不再等于 $c$，各损失一个；其他值既不是 $x$ 也不会变成 $c$。证毕。

引理 2

对固定 $x$，最优操作的净增量是对应 $+1/-1/0$ 序列的最大子段和。

证明：每个可选区间与该序列的一个连续子段一一对应，由引理 1，其子段和恰为操作净增量。证毕。

引理 3

线性 DP 更新后，best[x] 是以当前 $x$ 位置结尾的最大净增量。

证明：一个最优子段要么从当前 $x$ 重新开始，值为 $1$；要么延续到上一次 $x$ 结尾的最优子段，中间只有新出现的 $c$ 会降低净增量，再加入当前 $x$ 的贡献 $1$。转移恰取二者最大。证毕。

定理

算法输出操作后 $c$ 的最大频率。

证明：由引理 2，枚举全部 $x$ 的最大子段和覆盖所有非零操作；引理 3 保证线性 DP 准确求得这些最大值。再加上原有 $c$ 数量，并允许净增量为 $0$，即得到全局最优。证毕。

复杂度

满分算法时间复杂度为 $O(n)$，空间复杂度为 $O(\max a_i)$。