G2. 大胜！ (困难版)

问题要求我们找到一个子数组 $a[l, r]$，使得 $med(a[l, r]) - min(a[l, r])$ 最大化。这里，$med$ 是中位数（排序后长度为 $k$ 的子数组中位于位置 $\lceil (k+1)/2 \rceil$ 的元素），$min$ 是最小元素。约束条件 $a_i \le n$ 对所提供的解法至关重要。

让我们逐步分解这个解法。

1. 重新表述目标和高层方法：

目标是最大化 $MED - MN$，其中 $MED$ 是中位数，$MN$ 是子数组的最小值。 该解法提出了一种类似双指针的方法。它固定一个候选的最小值 $MN$，然后尝试找到一个可能的最大候选中位数值 $MED$，使得存在一个子数组，其最小值恰好是 $MN$，中位数至少是 $MED$。

2. 固定最小值 ($MN$) 并刻画子数组：

对于一个固定的 $MN$，任何最小值为 $MN$ 的子数组 $a[l, r]$ 必须满足两个条件：

• 它必须包含至少一个元素 $a_u = MN$。
• 子数组 $a[l, r]$ 内的所有元素 $a_i$ 都必须大于或等于 $MN$（即，对于 $l \le i \le r$，$a_i \ge MN$）。

为了高效地处理第二个条件，该解法使用了“$a_u$ 是严格最小值的最大区间”的概念。对于每个索引 $u$，我们找到 $l_u$ 和 $r_u$：

• $l_u$：$u$ 左侧第一个使得 $a_{l_u} < a_u$ 的索引（如果没有则为 $0$）。这意味着 $(l_u, u]$ 中的所有元素都 $\ge a_u$。
• $r_u$：$u$ 右侧第一个使得 $a_{r_u} < a_u$ 的索引（如果没有则为 $n+1$）。这意味着 $[u, r_u)$ 中的所有元素都 $\ge a_u$。

这些 $l_u$ 和 $r_u$ 的值可以使用单调栈在 $O(n)$ 时间内为所有 $u$ 计算出来。具体来说，对于给定的 $u$，$l_u$ 是其左侧第一个值 小于 $a_u$ 的元素的索引，$r_u$ 是其右侧第一个值 小于 $a_u$ 的元素的索引。所以，任何以 $a_u$ 为最小值且 $a_u = MN$ 的子数组 $a[l, r]$ 都必须满足 $l_u < l \le u \le r < r_u$。

3. 为中位数检查定义 sign 数组：

对于一个给定的潜在中位数值 $M$，我们定义一个 sign 数组：

• 如果 $a_i \ge M$，则 sign_i = +1
• 如果 $a_i < M$，则 sign_i = -1

一个关键的洞察是：一个子数组 $a[l, r]$ 的中位数 $\ge M$ 当且仅当该子数组上 sign 值的和为正。 设 $k = r - l + 1$ 为子数组的长度。中位数 $\ge M$ 的条件是至少有 $\lceil (k+1)/2 \rceil$ 个元素 $\ge M$。 如果 $S$ 是 $a[l, r]$ 中 sign 值的和，设 $N_+$ 是 $\ge M$ 的元素数量，$N_-$ 是 $< M$ 的元素数量。 那么 $S = N_+ \cdot (+1) + N_- \cdot (-1) = N_+ - N_-$。 同时，$N_+ + N_- = k$。所以 $N_- = k - N_+$。 代入得，$S = N_+ - (k - N_+) = 2 N_+ - k$。 条件 $N_+ \ge \lceil (k+1)/2 \rceil$ 等价于 $2 N_+ \ge 2 \lceil (k+1)/2 \rceil$。 如果 $k$ 是奇数，$k = 2p+1$，则 $\lceil (k+1)/2 \rceil = p+1$。所以 $2 N_+ \ge 2p+2 = k+1$。这意味着 $2 N_+ - k \ge 1$，即 $S \ge 1$。 如果 $k$ 是偶数，$k = 2p$，则 $\lceil (k+1)/2 \rceil = p+1$。所以 $2 N_+ \ge 2p+2 = k+2$。这意味着 $2 N_+ - k \ge 2$，即 $S \ge 2$。 然而，问题陈述中关于“至少一半元素是高的”的说法将此简化为“该区间上 sign 的总和为正”。这是中位数问题中常用的一个技巧。如果和为正，则意味着 $N_+ > N_-$，并且由于 $N_+ + N_- = k$，这意味着 $N_+ > k/2$，这正是我们需要的使中位数 $\ge M$ 的条件。

现在，对于一个特定的位置 $u$ 成为子数组 $a[l, r]$ 的最小值 $MN$： 子数组 $a[l, r]$ 必须在 $(l_u, r_u)$ 范围内（即 $l_u < l \le u \le r < r_u$）。 $a[l, r]$ 的 signs 之和必须为正。 为了最大化固定 $u$（即 $a_u = MN$）的 signs 之和，我们需要找到最好的 $l$ 和 $r$。 $a[l, r]$ 的 signs 之和为 $sign_u + \sum_{i=l}^{u-1} sign_i + \sum_{i=u+1}^{r} sign_i$。 为了最大化这个和，我们需要选择 $l$ 使得 $\sum_{i=l}^{u-1} sign_i$ 最大化（这是在范围 $(l_u, u-1]$ 内以 $u-1$ 结尾的 maxSuffix 和），并选择 $r$ 使得 $\sum_{i=u+1}^{r} sign_i$ 最大化（这是在范围 $[u+1, r_u)$ 内以 $u+1$ 开始的 maxPrefix 和）。 因此，对于给定的 $u$，存在这样一个子数组的条件是： maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0（或 > 0，取决于中位数定义的严格性。提供的解法中说 >=0 表示 ‘正’，我们暂时遵循这个，假设它能正确处理边界情况或进行了简化。中位数和的通常解释是 > 0。） 这里，maxSuffix(A, B) 表示 sign 数组在范围 $[A, B]$ 内的最大后缀和，maxPrefix(A, B) 表示 sign 数组在范围 $[A, B]$ 内的最大前缀和。如果 $A > B$，这些和为 $0$。

4. 使用线段树：

为了高效地计算任意范围内的 maxSuffix、maxPrefix 和总和，我们使用线段树。线段树中的每个节点存储：

• totalSum: 其范围内 sign 值的和。
• bestPrefix: 其范围内的最大前缀和。
• bestSuffix: 其范围内的最大后缀和。
• ans: 其范围内的最大子数组和（类似Kadane算法）。（虽然解法只提到了 ans, bestPrefix, bestSuffix, totalSum，但这里的 ans 可能指的是该段内任何子数组的最大和，这在我们需要通用最大和时可能有用，但对于我们问题中特定的 maxSuffix/maxPrefix，其他三个更相关。）

当合并两个子节点（左孩子 $L$，右孩子 $R$）时：

• totalSum = L.totalSum + R.totalSum
• bestPrefix = max(L.bestPrefix, L.totalSum + R.bestPrefix)
• bestSuffix = max(R.bestSuffix, R.totalSum + L.bestSuffix) maxSuffix(l_u, u-1) 和 maxPrefix(u+1, r_u) 的查询可以在这个线段树上以 $O(\log n)$ 的时间完成。

5. 主算法循环：

算法从 $1$ 到 $N$ 遍历 MN。在这个循环内部，它试图找到可能的最大 MED。

初始化：

• 构建线段树。初始时，假设 MED = 1。由于所有 $a_i \ge 1$，所有 $a_i \ge MED$，所以对所有 $i$，sign_i = +1。线段树以所有 sign_i = +1 初始化。
• current_MED = 1。
• max_diff = 0。

外层循环（遍历 MN 从 1 到 $N$）：

对于每个 MN：

1. 将 MN 视为最小值： 识别所有 $a_u = MN$ 的索引 $u$。对于每个这样的 $u$，我们需要检查是否能用 当前 的 current_MED 满足条件 maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0。注意，sign_u 的值是 +1 如果 $a_u \ge current\_MED$，是 -1 如果 $a_u < current\_MED$。由于我们固定 $a_u = MN$，这意味着 $MN \ge current\_MED$ 或 $MN < current\_MED$。

2. 内层循环（递增 current_MED）： 这是核心的贪心部分。只要对于 所有 $a_u \ge MN$ 的索引 $u$（并且 $a_u$ 可能是一个中位数至少为 current_MED 的子数组的最小值），条件 maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 都满足，我们就将 current_MED 增加 1。 随着 current_MED 的增加，一些之前 $\ge current\_MED$ 的值 $a_i$ 现在可能变得 $< current\_MED$。对于这些位置，它们的 sign_i 从 $+1$ 变为 $-1$。这需要在段树中进行点更新。具体来说，对于每个使得 $a_i = current\_MED - 1$ 的位置 $i$（即，$a_i$ 刚刚好 $\ge current\_MED - 1$ 并且现在 $< current\_MED$），我们将 sign_i 更新为 $-1$。 （更准确地说，我们增加 current_MED。然后，所有 $a_i = current\_MED - 1$ 的位置 $i$ 在段树中都必须从 $+1$ 更新为 $-1$。）

3. 当条件失败时： 当对于 任何 $a_u = MN$ 的索引 $u$，不等式 maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 失败时，这意味着我们无法找到一个最小值为 $MN$ 且中位数 $\ge current\_MED$ 的子数组。所以，对于这个 $MN$，可能的最大中位数是 current_MED - 1。

4. 记录最大差值： 更新 max_diff = max(max_diff, (current_MED - 1) - MN)。

5. 推进 MN： 在移动到下一个 MN 之前，我们需要确保等于 当前 MN 的元素不能成为中位数为 current_MED 的子数组的一部分，如果它们的 sign 贡献是关键的话。解法通过向上迭代 MN 来隐式处理这一点。随着 MN 的增加，元素 $a_i = MN$ 现在被“锁定”为潜在的最小值。如果 MN < current_MED，它们的 sign_u 将是 $-1$；如果 MN >= current_MED，则是 $+1$。

精化的内层循环/更新：

内层循环的描述有点微妙。让我们澄清一下 current_MED 和 MN 的交互。

$l_u, r_u$ 的值是基于 $a_u$（索引 $u$ 处的值），而不是 $MN$。它们只计算一次。 sign 数组取决于 current_MED。

一个更精确的 MN 迭代流程：

对于 $MN = 1 \dots N$:

1. 检查 MN 之前： while current_MED <= N: 遍历所有 $a_i == current_MED - 1$ 的索引 i。对于每个这样的 i，在线段树中将 sign_i 从 $+1$ 更新为 $-1$。 （此步骤确保 sign 数组始终反映当前的 current_MED。）

   现在，检查是否存在 任何 $a_u = MN$ 的索引 u（我们正在考虑的当前最小值），使得对于当前的 current_MED，条件 maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 不 满足。 对于 特定 元素 $a_u=MN$ 的 sign_u 条件是：

   • 如果 $MN \ge current\_MED$，则 $sign_u = +1$。
   • 如果 $MN < current\_MED$，则 $sign_u = -1$。 所以，对于每个 $a_u = MN$ 的 $u$，我们需要评估： max_possible_sum_for_u = maxSuffix(l_u, u-1) + (MN >= current_MED ? 1 : -1) + maxPrefix(u+1, r_u)

   如果对于 任何 $a_u=MN$ 的 $u$，max_possible_sum_for_u < 0，那么我们无法用 $MN$ 作为最小值实现中位数为 current_MED。在这种情况下，我们跳出内层循环（不能为这个 MN 进一步增加 current_MED）。对于这个 MN，最好的中位数是 current_MED - 1。更新 max_diff = max(max_diff, (current_MED - 1) - MN)。 否则（如果对于所有 $a_u=MN$ 的 $u$，max_possible_sum_for_u >= 0），那么我们可能可以实现中位数为 current_MED。所以，我们增加 current_MED 并继续内层 while 循环。

这个逻辑似乎与“贪心提升 med”部分更一致。从 +1 变为 -1 的值是那些变得 小于 当前 med 的值。

数据结构和复杂度：

• 单调栈： 为所有 $u$ 计算 $l_u$ 和 $r_u$：$O(N)$ 时间。
• 线段树：
  • 初始化：$O(N)$
  • 点更新：$O(\log N)$
  • 范围查询（用于 maxSuffix, maxPrefix）：$O(\log N)$
• 主循环：
  • 外层循环从 $1$ 到 $N$ 遍历 MN。
  • 内层 while current_MED 循环意味着 current_MED 在所有 MN 迭代中也从 $1$ 到 $N$ 整体 递增。每次 current_MED 增加，我们对所有元素 $a_i = current\_MED - 1$ 进行点更新。由于每个 $a_i$ 值只出现一次，每个索引 $i$ 的 sign 从 $+1$ 变为 $-1$ 最多更新一次。这总共为 current_MED 的推进提供了 $O(N \log N)$ 的时间。
  • 对于每个 MN，我们遍历所有 $a_u = MN$ 的 $u$。假设有 $C_{MN}$ 个这样的索引。对于每个索引，我们进行两次范围查询（每次 $O(\log N)$）。所有 MN 的 $C_{MN}$ 之和为 $N$。所以，所有 MN 的所有查询总共是 $O(N \log N)$。

因此，总时间复杂度为 $O(N \log N)$。 内存复杂度为 $O(N)$，用于数组、栈和线段树。

正确性为何：

• 贪心 MED： 对于每个固定的 MN，内层循环正确地找到了可以实现的最大 MED。如果 MED 可以是 $X$，它也可以是 $X-1$。所以我们尝试将其推到尽可能高。
• 迭代 MN： 通过从 $1$ 到 $N$ 迭代 MN，我们保证考虑了子数组的每个可能的最小值。
• 用于 sign 和的线段树： 线段树正确地维护了必要的信息（maxPrefix, maxSuffix）来检查在计算的 $[l_u, r_u)$ 范围内的任何潜在子数组的中位数条件。条件 maxSuffix(l_u, u-1) + sign_u + maxPrefix(u+1, r_u) >= 0 找到了以 $u$ 为中心（其中 $u$ 是最小值 $MN$）并向左延伸至 $l_u$、向右延伸至 $r_u$ 的任何子数组的最大可能 signs 之和。如果这个最大可能和 $\ge 0$，那么这样的子数组就存在，满足中位数属性。

示例演练（概念性）：

设 $a = [1, 4, 1, 5, 3, 3]$, $n=6$.

1. 预计算 $l_u, r_u$： （粗略地说，取决于严格不等式与等式。在解释中，我们假设 $l_u, r_u$ 值的定义是严格的） $l_u$：$u$ 左侧第一个索引，其值 $a[l_u] < a[u]$ $r_u$：$u$ 右侧第一个索引，其值 $a[r_u] < a[u]$

   对于 $a_1=1$: $l_1=0, r_1=7$ (没有更小的元素) 对于 $a_2=4$: $l_2=1$ (因为 $a_1=1<4$), $r_2=7$ (在 $a_2$ 右侧没有 $a_i<4$) … 这很复杂，我们只使用给定的严格定义“左侧第一个值 < a[u]+1”和“右侧第一个值 < a[u]-1”。这似乎不寻常。范围最小值查询的标准通常是“第一个小于 $a_u$ 的元素”。我们假设标准的 $L_u, R_u$，其中 $a_u$ 是 $a[L_u \dots R_u]$ 中的最小值。

   让我们使用典型定义：$L[i]$ 是第一个索引 $j < i$ 使得 $A[j] < A[i]$，$R[i]$ 是第一个索引 $j > i$ 使得 $A[j] < A[i]$。如果不存在这样的索引，我们可以使用 0 和 $n+1$。 对于 $a = [1,4,1,5,3,3]$: $L = [0, 1, 0, 3, 3, 3]$ (索引 0 是哨兵) $R = [7, 3, 7, 5, 7, 7]$ (索引 7 是哨兵)

   对于 $u=1, a_1=1: L_1=0, R_1=7$ 对于 $u=2, a_2=4: L_2=1, R_2=3$ (因为 $a_3=1<4$) 对于 $u=3, a_3=1: L_3=0, R_3=7$ 对于 $u=4, a_4=5: L_4=3, R_4=5$ (因为 $a_5=3<5$) 对于 $u=5, a_5=3: L_5=3, R_5=7$ 对于 $u=6, a_6=3: L_6=5, R_6=7$

2. 初始化线段树： current_MED = 1。所有 $a_i \ge 1$，所以 sign = [1,1,1,1,1,1]。

3. 外层循环：MN = 1 $a_u = 1$ 的索引 $u$：$u=1, u=3$。

   内层 while 循环 (对于 current_MED):

   • current_MED = 1:

     • 对于 $u=1, a_1=1$: $L_1=0, R_1=7$。$MN \ge current\_MED$ (1>=1)，所以 $sign_1=+1$。 maxSuffix(0,0) (空) 是 0。maxPrefix(2,6): sign 数组是 $[1,1,1,1,1,1]$。$[1,1,1,1,1]$ 的最大前缀是 $5$。 对于 $u=1$ 的和：$0 + 1 + 5 = 6 \ge 0$。OK。
     • 对于 $u=3, a_3=1$: $L_3=0, R_3=7$。$MN \ge current\_MED$ (1>=1)，所以 $sign_3=+1$。 maxSuffix(0,2): sign 对于 $[1,4,1]$ 是 $[1,1,1]$。$[1,1]$ 的最大后缀是 2。 maxPrefix(4,6): sign 对于 $[5,3,3]$ 是 $[1,1,1]$。$[1,1,1]$ 的最大前缀是 3。 对于 $u=3$ 的和：$2 + 1 + 3 = 6 \ge 0$。OK。 对于 MN=1 和 current_MED=1 都 OK。将 current_MED 增加到 2。

   • current_MED = 2: 为 $a_i = 1$ 更新 sign (等于 current_MED - 1 的值)。索引 $i=1,3$ 现在 $a_i < 2$，所以更新 sign_1=-1, sign_3=-1。 sign 数组现在是 [-1, 1, -1, 1, 1, 1]。

     检查 $u=1, a_1=1$: $L_1=0, R_1=7$。$MN < current\_MED$ (1<2)，所以 $sign_1=-1$。 maxSuffix(0,0) 是 0。maxPrefix(2,6) 在 [-1, 1, 1, 1, 1] 中是 $a[2 \dots 6]$ ($[4,1,5,3,3]$) 或 signs $s[2 \dots 6]$ (值 $[1,-1,1,1,1]$) 的最大前缀。$[1,-1,1,1,1]$ 的最大前缀是 $1$ (对于 $a_2=4$)。 对于 $u=1$ 的和：$0 + (-1) + 1 = 0 \ge 0$。OK。 检查 $u=3, a_3=1$: $L_3=0, R_3=7$。$MN < current\_MED$ (1<2)，所以 $sign_3=-1$。 maxSuffix(0,2) 在 [-1,1,-1] 中：[-1,1] 的最大后缀是 $1$。 maxPrefix(4,6) 在 [1,1,1] 中：$[1,1,1]$ 的最大前缀是 $3$。 对于 $u=3$ 的和：$1 + (-1) + 3 = 3 \ge 0$。OK。 对于 MN=1 和 current_MED=2 都 OK。将 current_MED 增加到 3。

   • current_MED = 3: 为 $a_i = 2$ 更新 sign (无)。 sign 数组仍然是 [-1, 1, -1, 1, 1, 1]。

     检查 $u=1, a_1=1$: $L_1=0, R_1=7$。$MN < current\_MED$ (1<3)，所以 $sign_1=-1$。 maxSuffix(0,0) 是 0。maxPrefix(2,6) 在 [1,-1,1,1,1] 中是 1。 对于 $u=1$ 的和：$0 + (-1) + 1 = 0 \ge 0$。OK。 检查 $u=3, a_3=1$: $L_3=0, R_3=7$。$MN < current\_MED$ (1<3)，所以 $sign_3=-1$。 maxSuffix(0,2) 在 [-1,1,-1] 中是 1。 maxPrefix(4,6) 在 [1,1,1] 中是 3。 对于 $u=3$ 的和：$1 + (-1) + 3 = 3 \ge 0$。OK。 对于 MN=1 和 current_MED=3 都 OK。将 current_MED 增加到 4。

   • current_MED = 4: 为 $a_i = 3$ 更新 sign。索引 $i=5,6$ 现在 $a_i < 4$，所以更新 sign_5=-1, sign_6=-1。 sign 数组现在是 [-1, 1, -1, 1, -1, -1]。

     检查 $u=1, a_1=1$: $L_1=0, R_1=7$。$MN < current\_MED$ (1<4)，所以 $sign_1=-1$。 maxSuffix(0,0) 是 0。maxPrefix(2,6) 在 [1,-1,1,-1,-1] 中：$[1,-1,1,-1,-1]$ 的最大前缀是 $1$。 对于 $u=1$ 的和：$0 + (-1) + 1 = 0 \ge 0$。OK。 检查 $u=3, a_3=1$: $L_3=0, R_3=7$。$MN < current\_MED$ (1<4)，所以 $sign_3=-1$。 maxSuffix(0,2) 在 [-1,1,-1] 中是 1。 maxPrefix(4,6) 在 [1,-1,-1] 中：$[1,-1,-1]$ 的最大前缀是 $1$。 对于 $u=3$ 的和：$1 + (-1) + 1 = 1 \ge 0$。OK。 对于 MN=1 和 current_MED=4 都 OK。将 current_MED 增加到 5。

   • current_MED = 5: 为 $a_i = 4$ 更新 sign。索引 $i=2$ 现在 $a_2 < 5$，所以更新 sign_2=-1。 sign 数组现在是 [-1, -1, -1, 1, -1, -1]。

     检查 $u=1, a_1=1$: $L_1=0, R_1=7$。$MN < current\_MED$ (1<5)，所以 $sign_1=-1$。 maxSuffix(0,0) 是 0。maxPrefix(2,6) 在 [-1,-1,1,-1,-1] 中：$[-1,-1,1,-1,-1]$ 的最大前缀是 $1$ (对于 $a_4=5$)。 对于 $u=1$ 的和：$0 + (-1) + 1 = 0 \ge 0$。OK。 检查 $u=3, a_3=1$: $L_3=0, R_3=7$。$MN < current\_MED$ (1<5)，所以 $sign_3=-1$。 maxSuffix(0,2) 在 [-1,-1,-1] 中是 $-1$。 maxPrefix(4,6) 在 [1,-1,-1] 中是 $1$。 对于 $u=3$ 的和：$(-1) + (-1) + 1 = -1 < 0$。失败！ 条件对于 $u=3$ 失败。所以，对于 MN=1，最大 MED 是 current_MED - 1 = 4。 max_diff = max(0, 4 - 1) = 3。

4. 外层循环：MN = 2 (示例中没有元素为2)

5. 外层循环：MN = 3 $a_u = 3$ 的索引 $u$：$u=5, u=6$。

   current_MED 应从上次离开的地方继续，即 $5$。 sign 数组是 [-1, -1, -1, 1, -1, -1]。

   检查 $u=5, a_5=3$: $L_5=3, R_5=7$。$MN < current\_MED$ (3<5)，所以 $sign_5=-1$。 maxSuffix(3,4) 在 [1,-1] 中是 1。（来自 $a_4=5, a_5=3$。Signs: $s_4=1, s_5=-1$。对于范围 $a_3 \dots a_4$ 的 $s_3=1, s_4=-1$ 的后缀是 $s_4=1$ 如果 $a_4 \ge MED$, $s_4=-1$ 如果 $a_4 < MED$。对于 $a_4=5$, 当前 $MED=5$ 时 $s_4=1$。对于 $a_3=1$, $s_3=-1$。所以 [-1,1]。最大后缀和是 1。） maxPrefix(6,6) 在 [-1] 中是 -1。 对于 $u=5$ 的和：$1 + (-1) + (-1) = -1 < 0$。失败！ 条件对于 $u=5$ 失败。所以对于 MN=3，最大 MED 是 current_MED - 1 = 4。 max_diff = max(3, 4 - 3) = 3。

…依此类推。逻辑似乎成立。示例子数组 $a[2,5]=[4,1,5,3]$，其 $med=4, min=1$ 得到 $4-1=3$。我们的算法为 $MN=1$ 找到了 $MED=4$，差值为 $3$。

该解法巧妙地利用了线段树和 sign 数组来高效地检查中位数条件。对 MN 的扫描和对 MED 的贪心递增确保了所有最优解都被考虑到。