问题重述

给定序列 $a_1, a_2, \ldots, a_n$，可以执行一次操作：选择区间 $[l, r]$ 和整数 $k$，将区间内所有数加上 $k$。要求最大化最终序列的众数出现次数，并找出所有可能成为众数的值。

---

关键观察

1. 操作的本质

操作相当于：我们可以将任意一个连续区间内的数整体平移到另一个值。

这意味着：

• 我们可以让某个区间内的数都变成同一个目标值
• 目标值可以是任意整数（受 $k$ 范围限制，但范围很大）

2. 问题转化

设目标众数值为 $x$。我们希望通过操作，让尽可能多的数等于 $x$。

对于每个位置 $i$：

• 如果 $a_i = x$，那么它自然就是 $x$，不需要修改
• 如果 $a_i \neq x$，我们可以通过修改包含 $i$ 的区间，将 $a_i$ 变成 $x$

关键限制：所有被修改的位置必须在同一个连续区间内。

---

核心解法

1. 按数值分组

首先，将序列中所有等于某个值 $v$ 的位置找出来。设 $pos_v$ 是 $v$ 出现的所有位置。

我们的目标是：对于每个候选值 $v$，计算通过一次区间修改，最多能让多少个位置变成 $v$。

2. 区间修改的收益分析

假设我们选择目标值为 $v$，考虑哪些位置可以变成 $v$：

• 原本就是 $v$ 的位置：直接贡献 $1$
• 原本是其他值的位置：如果它们在一个连续的修改区间内，且通过加上某个 $k$ 能变成 $v$，那么也可以贡献 $1$

重要性质：对于固定的目标值 $v$，一个值 $u$ 能通过区间修改变成 $v$ 当且仅当 $u + k = v$ 对于某个 $k$ 成立。但由于 $k$ 可以任意选择，实际上任何值都可以通过区间修改变成 $v$！

因此，问题简化为：选择一个区间 $[l, r]$，让区间内的所有数都变成 $v$，同时区间外的 $v$ 保持不变。

---

算法框架

1. 问题重新表述

对于候选值 $v$，设：

• $cnt_v$ = $v$ 在原始序列中的出现次数
• 我们选择一个区间 $[l, r]$，区间内原本不是 $v$ 的数通过修改变成 $v$
• 区间外原本是 $v$ 的数保持不变

那么最终 $v$ 的出现次数 = $cnt_v$ + $(r-l+1)$ - (区间内原本是 $v$ 的个数)

2. 最大化策略

对于固定的 $v$，定义序列 $b$：

• 如果 $a_i = v$，则 $b_i = -1$（修改这个位置会减少 $v$ 的数量）
• 如果 $a_i \neq v$，则 $b_i = +1$（修改这个位置会增加 $v$ 的数量）

那么问题转化为：在 $b$ 序列中找一个区间 $[l, r]$，使得区间和最大。

这是一个经典的最大子段和问题！

3. 最终计算

对于值 $v$，最大出现次数 = $cnt_v$ + (最大子段和)

我们需要对所有不同的 $v$ 计算这个值，然后取最大值。

---

具体实现

1. 预处理

• 用哈希表记录每个值出现的位置
• 对每个值 $v$，构建对应的 $b$ 序列

2. 最大子段和计算

使用 Kadane 算法在 $O(n)$ 时间内计算最大子段和：

def max_subarray_sum(arr):
    max_ending_here = max_so_far = 0
    for x in arr:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

3. 对所有值计算

对于每个值 $v$：

• 如果 $v$ 出现次数很少，直接构建 $b$ 序列计算
• 如果 $v$ 出现次数很多，可以优化：实际上只需要在 $v$ 出现的位置附近计算

---

复杂度优化

直接对每个值构建 $b$ 序列是 $O(n^2)$ 的，不可行。

关键优化：实际上，我们只需要考虑那些在序列中出现过的值作为候选目标值。

对于每个候选值 $v$，我们只需要在它的出现位置附近计算最大子段和，因为：

• $b$ 序列中只有 $v$ 出现的位置是 $-1$，其他位置是 $+1$
• 最大子段和一定出现在某个 $v$ 出现位置的附近

具体来说，我们可以：

1. 对序列离散化
2. 对每个值 $v$，记录所有出现位置 $pos_v$
3. 对于每个 $v$，在 $pos_v$ 的附近窗口内计算最大子段和

---

边界情况

1. 全序列相同

题目保证 $a_i$ 不全相等，所以不需要特殊处理。

2. 最大出现次数为 $n$

如果最大子段和 = $n - cnt_v$，说明可以通过一次修改让所有数变成 $v$。

3. 多个值达到最大出现次数

需要记录所有达到最大出现次数的 $v$ 值。

---

最终算法

1. 离散化：将 $a_i$ 映射到 $[1, m]$
2. 分组：记录每个值出现的位置
3. 计算最大值：
   • 初始化 $max\_freq = 0$, $candidates = \{\}$
   • 对每个值 $v$：
     • $base = cnt_v$
     • 在 $v$ 的出现位置附近计算最大子段和 $max\_sum$
     • $total = base + max\_sum$
     • 如果 $total > max\_freq$，更新 $max\_freq$ 和 $candidates$
     • 如果 $total = max\_freq$，将 $v$ 加入 $candidates$
4. 输出：$max\_freq$ 和排序后的 $candidates$

---

复杂度分析

• 离散化：$O(n \log n)$
• 最大子段和计算：每个值 $v$ 的处理与它的出现次数相关，总复杂度 $O(n)$
• 总复杂度：$O(n \log n)$，适合 $n \le 2 \times 10^5$

---

总结

这道题的核心在于：

1. 问题转化：将区间修改问题转化为最大子段和问题
2. 收益分析：分析修改不同位置对目标值出现次数的影响
3. 算法优化：利用出现位置的局部性优化计算
4. 多候选处理：找出所有可能达到最大出现次数的值

通过将复杂的区间操作问题转化为经典的最大子段和问题，我们得到了一个高效且优雅的解法。