# C

# 题目大意

给定两个数 $n$ 和 $k$，再给一个数列 $A = (a_1, ..., a_n)$
你可以对任意一个区间 $[l, r]$ 中的数进行操作，使他们全都加上 $k$。你也可以不做这个操作

请问，这个数列，众数的出现个数的最大值是多少？

# 数据范围

• $1 \le n \le 10^6$
• $-10^6 \le k,a_i \le 10^6$

# 题解

显然，当 $k$ 为 $0$ 时，答案就是一开始初始数组的个数

转换一下题目，其实是，你对于一个目标值 $t$，然后使得 整个数列中 t 的个数 + 选择区间内 t - k 的个数 - 选择区间内 t 的个数
也就是说，我们对于给定的 $t$，要使得 区间内 t - k 的个数 - 区间内 t 的个数 最大化（区间子段和最大化）

显然，可以用 $O(n)$ 处理一个指定的 $t$，而 $t$ 是$A$ 数组中，不同的数，也就是，复杂度会到 $O(N^2)$，这是不可接受的
但我们可以发现，每个位置只会影响两个值 t = a[i] 贡献 $-1$ 和 t = a[i] + k 贡献 $+1$