G1. 大胜！ (简单版)

问题描述

这是问题的简单版本。版本之间的区别在于，在此版本中 $a_i \leq \min(n, 100)$。

给定一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$。

你的任务是找到一个子数组 $a[l,r]$（一个连续的元素序列 $a_l, a_{l+1}, \ldots, a_r$），使得表达式 $\text{med}(a[l,r]) - \min(a[l,r])$ 的值最大化。

这里：

• $\text{med}$ — 子数组的中位数，即子数组排序后位于位置 $\lceil \frac{k+1}{2} \rceil$ 的元素，其中 $k$ 是其长度；
• $\min$ — 该子数组的最小元素。

示例

例如，考虑数组 $a = [1, 4, 1, 5, 3, 3]$ 并选择子数组 $a[2,5] = [4, 1, 5, 3]$。排序后，它看起来像 $[1, 3, 4, 5]$。

• $\text{med}(a[2,5]) = 4$，因为 $\lceil \frac{4+1}{2} \rceil = 3$，所以排序后子数组中的第三个元素是 4；
• $\min(a[2,5]) = 1$，因为最小元素是 1。

在这个例子中，$\text{med} - \min = 4 - 1 = 3$。

输入

第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ — 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq \min(n, 100))$ — 数组的元素。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 — 数组所有子数组中 $\text{med} - \min$ 的最大可能值。

题解概述

问题要求我们找到一个子数组 $a[l, r]$，使得 $med(a[l, r]) - min(a[l, r])$ 最大化。约束条件 $a_i \le \min(n, 100)$ 在这里至关重要，因为它将数组中的可能值限制在一个很小的范围内（1到100）。

所提供的解法利用了这个小的值范围，通过遍历所有可能的中位数值。

以下是解法的详细分解：

理解策略：遍历中位数 ($m$)

核心思想是固定一个潜在的中位数值，我们称之为 $m$。由于数组的值在1到100之间，$m$ 也只能在1到100之间。我们将尝试这100个可能的 $m$ 值。

对于一个固定的 $m$，我们的目标是找到一个子数组 $a[l, r]$，使得：

1. $med(a[l, r]) \ge m$ (中位数至少为 $m$)
2. 我们想要最大化 $m - min(a[l, r])$。这意味着我们想找到一个中位数至少为 $m$ 且其最小元素尽可能小的子数组。

固定中位数 $m$ 的分步解释：

1. 将数组转换为 $b$： 对于一个固定的 $m$，我们创建一个与 $a$ 大小相同的新数组 $b$。每个元素 $b_j$ 的确定如下：

   • 如果 $a_j \ge m$，则 $b_j = +1$
   • 如果 $a_j < m$，则 $b_j = -1$

   为什么这样转换？ 中位数的定义依赖于大多数元素。一个子数组 $a[l, r]$ 的中位数至少为 $m$ 当且仅当其一半以上的元素 $\ge m$。 如果我们对一个子数组 $a[l, r]$ 的 $b_j$ 值求和（我们称之为 $S$），这个和将告诉我们大于等于 $m$ 的元素数量与小于 $m$ 的元素数量的对比。

   • 每个 $a_j \ge m$ 对和的贡献是 $+1$。
   • 每个 $a_j < m$ 对和的贡献是 $-1$。 如果和 $S > 0$，意味着子数组中 $\ge m$ 的元素多于 $< m$ 的元素。这确保了子数组的中位数至少为 $m$。（具体来说，对于长度为 $k$ 的子数组，如果 $\ge m$ 的元素数量为 $C_{ge}$，$< m$ 的元素数量为 $C_{lt}$，那么 $S = C_{ge} - C_{lt}$。如果 $S > 0$，则 $C_{ge} > C_{lt}$。由于 $C_{ge} + C_{lt} = k$，这意味着 $C_{ge} > k/2$。这正是中位数 $\ge m$ 的条件。）

2. 使用前缀和计算子数组和： 我们计算 $b$ 数组的前缀和：$pref_k = \sum_{i=1}^k b_i$。我们定义 $pref_0 = 0$。 一个子数组 $b[l, r]$ 的 $b$ 值之和是 $pref_r - pref_{l-1}$。 因此，条件“$med(a[l, r]) \ge m$”等价于“$pref_r - pref_{l-1} > 0$”，或 $pref_r > pref_{l-1}$。

3. 为潜在中位数寻找“有效”索引： 对于一个固定的 $m$，我们想知道每个位置 $j$ 是否可以成为 某个 中位数至少为 $m$ 的子数组的一部分。如果存在一个包含 $j$ 的子数组 $a[l, r]$ 使得 $med(a[l, r]) \ge m$，那么这是成立的。 这意味着我们需要检查是否存在一个 $l \le j \le r$ 使得 $pref_r > pref_{l-1}$。

   解法中提出了两个条件：

   • $min_{0 \le x < j} pref_x < pref_j$：这意味着在 $j$ 之前存在一个起点 $l-1 = x$ 使得 $pref_j - pref_x > 0$。换句话说，存在一个以 $j$ 结尾的子数组 $a[x+1, j]$，其中位数 $\ge m$。
   • $pref_{j-1} < max_{j \le x \le n} pref_x$：这意味着在 $j$ 或之后存在一个终点 $r = x$ 使得 $pref_x - pref_{j-1} > 0$。换句话说，存在一个以 $j$ 开始的子数组 $a[j, x]$，其中位数 $\ge m$。

   为了高效地检查每个 $j$ 的这些条件：

   • 前缀最小值 ($prefmn_j$): 计算 $prefmn_j = \min_{0 \le x \le j} pref_x$。这使我们能快速检查 $min_{0 \le x < j} pref_x < pref_j$。
   • 后缀最大值 ($suffmx_j$): 计算 $suffmx_j = \max_{j \le x \le n} pref_x$。这使我们能快速检查 $pref_{j-1} < max_{j \le x \le n} pref_x$。

   如果 $prefmn_{j-1} < pref_j$ 或 $pref_{j-1} < suffmx_j$（注意：索引可能需要根据0-索引与1-索引进行仔细调整，但概念是成立的），那么位置 $j$ 就可以是中位数 $\ge m$ 的子数组的一部分。

4. 最大化 $m - a_j$： 对于每个满足步骤3中任一条件的位置 $j$（意味着 $a_j$ 可以是中位数至少为 $m$ 的子数组的一部分），我们将 $a_j$ 视为该子数组的一个潜在最小元素。 如果我们将 $a_j$ 选为最小元素，并且我们知道存在一个包含 $j$ 且中位数至少为 $m$ 的子数组，那么我们可以实现一个值为 $m - a_j$ 的差。 我们想要最大化 $med - min$。由于我们固定了 $med \ge m$，要最大化 $m - min$，我们应该尽量减小 $min$。对于一个包含 $j$ 且中位数 $\ge m$ 的子数组，可能的最小 $min$ 就是 $a_j$ 本身，如果我们选择一个 $a_j$ 确实是最小值的子数组 $a[l, r]$。

   解法中说：“如果任一不等式成立，索引 $j$ 就可以位于某个中位数 $\ge m$ 的子数组中。我们可以自由地将该 $j$ 作为所选子数组的最小值，得到值 $a_j$。因此，对于那个 $j$ 我们可以实现差值 $m-a_j$。在所有满足测试的索引中，保留最大的差值。” 这是一个关键的简化。这意味着我们不需要为每个 $j$ 显式地找到 最优 子数组。如果 $j$ 可以是 任何 有效的中位数 $\ge m$ 的子数组的一部分，我们就 假设 我们可以形成一个 $a_j$ 是最小值且中位数 $\ge m$ 的子数组。这是一种贪心方法。

   所以，对于一个固定的 $m$，我们遍历所有 $j$ 从 $1$ 到 $n$。如果 $a_j$ 是“有效的”（可以是中位数 $\ge m$ 的子数组的一部分），我们就用 $m - a_j$ 更新我们目前找到的最大差值。

整体算法：

1. 初始化 max_difference = -infinity (或一个非常小的数)。
2. 遍历 m 从 1 到 100： a. 创建数组 b，其中如果 a[j] >= m 则 b[j] = +1，否则 b[j] = -1。 b. 计算 b 的前缀和 pref。（pref[0] = 0, pref[k] = pref[k-1] + b[k]） c. 计算 pref 的前缀最小值 prefmn。（prefmn[j] = min(prefmn[j-1], pref[j])） d. 计算 pref 的后缀最大值 suffmx。（suffmx[j] = max(suffmx[j+1], pref[j])） e. 遍历 j 从 1 到 n： i. 检查 prefmn[j-1] < pref[j] (以 $j$ 结尾且中位数 $\ge m$ 的子数组)。 ii. 检查 pref[j-1] < suffmx[j] (以 $j$ 开始且中位数 $\ge m$ 的子数组)。 iii. 如果任一条件成立，更新 max_difference = max(max_difference, m - a[j])。
3. 输出 max_difference。

复杂度：

• 时间复杂度：

  • 外层循环运行100次（对于 $m=1$ 到 $100$）。
  • 循环内部：
    • 构建 b：$O(n)$
    • 计算 pref：$O(n)$
    • 计算 prefmn：$O(n)$
    • 计算 suffmx：$O(n)$
    • 扫描 j 并更新 max_difference：$O(n)$
  • 总时间复杂度：$100 \times O(n) = O(100n)$。
  • 鉴于 $n \le 2 \cdot 10^5$，$100 \times 2 \cdot 10^5 = 2 \cdot 10^7$，这在4秒的时间限制内是完全可以接受的。

• 空间复杂度：

  • 我们需要 a, b, pref, prefmn, suffmx 的数组，大小均为 $O(n)$。
  • 总空间复杂度：$O(n)$。
  • 鉴于 $n \le 2 \cdot 10^5$，这在256MB的内存限制内是可行的。

示例演练（简化）：

设 $a = [1, 4, 1, 5, 3, 3]$

我们选择 $m=4$。

1. 为 $m=4$ 构建 $b$： $a_j \ge 4 \implies b_j = +1$ $a_j < 4 \implies b_j = -1$ $a = [1, 4, 1, 5, 3, 3]$ $b = [-1, +1, -1, +1, -1, -1]$

2. 前缀和 $pref$：($pref_0=0$) $pref = [0, -1, 0, -1, 0, -1, -2]$ (0-indexed $pref_0$ 到 $pref_6$)

3. 前缀最小值 $prefmn$： $prefmn = [0, -1, -1, -1, -1, -1, -2]$

4. 后缀最大值 $suffmx$：(假设 $suffmx_{n+1}$ 是 $-\infty$) $suffmx = [0, 0, 0, 0, 0, -1, -2]$ (从右到左: $\max(-2)$, $\max(-1, -2)$, $\max(0, -1)$, 等)

5. 遍历 $j$ 并检查有效性：

   • 对于 $j=1 (a_1=1)$: $prefmn_0=0, pref_1=-1$。$0 < -1$ 是 FALSE。$pref_0=0, suffmx_1=0$。$0 < 0$ 是 FALSE。$a_1$ 对 $m=4$ 无效。
   • 对于 $j=2 (a_2=4)$: $prefmn_1=-1, pref_2=0$。$-1 < 0$ 是 TRUE。$a_2$ 有效。$max\_difference = \max(-\infty, 4-4) = 0$。
   • 对于 $j=3 (a_3=1)$: $prefmn_2=-1, pref_3=-1$。$-1 < -1$ 是 FALSE。$pref_2=0, suffmx_3=0$。$0 < 0$ 是 FALSE。$a_3$ 对 $m=4$ 无效。
   • 对于 $j=4 (a_4=5)$: $prefmn_3=-1, pref_4=0$。$-1 < 0$ 是 TRUE。$a_4$ 有效。$max\_difference = \max(0, 4-5) = 0$。
   • 对于 $j=5 (a_5=3)$: $prefmn_4=-1, pref_5=-1$。$-1 < -1$ 是 FALSE。$pref_4=0, suffmx_5=-1$。$0 < -1$ 是 FALSE。$a_5$ 对 $m=4$ 无效。
   • 对于 $j=6 (a_6=3)$: $prefmn_5=-1, pref_6=-2$。$-1 < -2$ 是 FALSE。$pref_5=-1, suffmx_6=-2$。$-1 < -2$ 是 FALSE。$a_6$ 对 $m=4$ 无效。

对于 $m=4$，找到的最大差值为 $0$。

如果我们尝试 $m=3$： $a = [1, 4, 1, 5, 3, 3]$ $b = [-1, +1, -1, +1, +1, +1]$ $pref = [0, -1, 0, -1, 0, 1, 2]$ $prefmn = [0, -1, -1, -1, -1, -1, -1]$ $suffmx = [2, 2, 2, 2, 2, 2, 2]$

我们检查 $j=3 (a_3=1)$: $prefmn_2=-1, pref_3=-1$。$-1 < -1$ 是 FALSE。 $pref_2=0, suffmx_3=2$。$0 < 2$ 是 TRUE。$a_3$ 有效。 $max\_difference = \max(\text{current\_max}, 3 - a_3) = \max(\text{current\_max}, 3 - 1) = \max(\text{current\_max}, 2)$。

该解法的逻辑是合理的，并利用了数组中值的范围小的特点，高效地检查了所有可能的中位数值。

提交