P9842 [ICPC 2021 Nanjing R] Klee in Solitary Confinement

自从旅行者来到蒙德，蒙德的人们突然对计算机编程和算法产生了极大的兴趣，包括西风骑士团的火花骑士可莉。  被琴再次关进禁闭室后，可莉决定花时间学习著名的莫队算法，该算法可以在不进行修改的情况下以 $\mathcal{O}(n^{1.5})$ 的时间复杂度计算某些区间查询问题。 为了检查可莉是否真正掌握了该算法（或者实际上是在秘密制造另一个炸弹），琴给了她一个整数序列 $a_1, a_2, \cdots, a_n$ 和一些查询 $[l_i, r_i]$，要求她找到连续子序列 $a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i}$ 中的众数。众数是指在子序列中出现次数最多的数字。 在莫队算法的帮助下，可莉毫不费力地解决了这个问题，但她脑海中又出现了另一个问题。给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$ 和一个整数 $k$，你可以最多进行一次以下操作：选择两个整数 $l$ 和 $r$，使得 $1 \le l \le r \le n$，并 $a_i$ 加上 $k$，其中 $l \le i \le r$。注意可以选择不进行此操作。计算如果你选择最优地进行（或不进行）操作，整个序列的众数的最大出现次数。

每个测试文件中只有一个测试用例。 输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^6$，$-10^6 \le k \le 10^6$），表示序列的长度和要添加的数。 输入的第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$-10^6 \le a_i \le 10^6$），表示原始序列。

输出一行，包含一个整数，表示在最优地进行（或不进行）操作后，整个序列的众数的最大出现次数。

对于第一个样例测试用例，选择 $l = 1$ 和 $r = 2$，我们将得到序列 $\{4, 4, 4, 4, 4\}$。显然，众数是 $4$，出现了 $5$ 次。 对于第二个样例测试用例，选择 $l = 4$ 和 $r = 6$，我们将得到序列 $\{3, 2, 3, 3, 3, 3, 3\}$。众数是 $3$，出现了 $6$ 次。 对于第四个样例测试用例，选择不进行操作。众数是 $1$ 和 $-2$，它们都出现了 $3$ 次。 题面翻译由 ChatGPT-4o 提供。