# 短板翻盘题解

## 解法比较

出题人解法先用单调栈确定每个 $a_i$ 可以充当区间最小值的最大跨度，并对相等值采用固定归属。线段树维护 $b$ 区间的总和、最大／最小前缀和与后缀和。固定 $i$ 后，若 $a_i>0$ ，取左侧最大后缀、$b_i$ 与右侧最大前缀；若 $a_i<0$ ，改取两侧最小值；允许侧段为空。这样恰好枚举了包含 $i$ 且以它为最小值的最优区间。遍历所有 $i$ ，时间为 $O(n\log n)$ ，空间为 $O(n)$ .

Codex（GPT-6）采用的实现保留“按最小值归属区间”的分解，用笛卡尔树一次性组织这些跨度，再自底向上合并前缀和极值。每个节点只处理常数次，时间降为 $O(n)$ ，空间仍为 $O(n)$ .下文解释树与区间的对应及正负号处理；这项收益来自消除逐点线段树查询，而非改变目标函数。

## 用最小值划分区间

为 $a$ 建立最小笛卡尔树：中序遍历顺序是数组下标，父节点的值不大于子节点。值相同时让更靠左的下标优先，也就是按二元组 $(a_i,i)$ 比较大小。

从左到右扫描，用单调栈保存当前树最右侧的一条链。加入节点 $i$ 时：

1. 只要栈顶的值大于 $a_i$ ，就将它弹出。最后弹出的节点成为 $i$ 的左孩子；若没有弹出节点，则左孩子为空。
2. 若栈仍非空，将 $i$ 设为新栈顶节点的右孩子。
3. 将 $i$ 入栈。

这里严格使用“大于”判断，相等时不弹栈，从而让更靠左的节点优先。扫描结束后，栈底就是树根。每个下标入栈、出栈各至多一次，建树时间为 $O(n)$ .

设节点 $i$ 的子树对应连续区间 $[L,R]$ . 任何满足 $L\le l\le i\le r\le R$ 的区间都有最小值 $a_i$ . 反过来，每个非空区间都可以归到其两个端点在笛卡尔树上的最近公共祖先：该节点位于区间中，子树包含整个区间，节点值就是区间最小值。因此遍历每个节点的这类区间即可覆盖全部答案。

## 用前缀和选两端

令 $P_0=0$ ，$P_j=\sum_{k=1}^{j}b_k$ . 包含 $i$ 的区间和为 $P_r-P_{l-1}$ ，其中两个下标可以独立选择：

$$l-1\in[L-1,i-1],\qquad r\in[i,R]$$

- 若 $a_i>0$ ，应最大化区间和，即右侧最大前缀和减去左侧最小前缀和。
- 若 $a_i<0$ ，应最小化区间和，即右侧最小前缀和减去左侧最大前缀和。
- 若 $a_i=0$ ，乘积为 $0$ .

对每个子树，保存下标范围 $[L-1,R]$ 内前缀和的最小值和最大值。注意，这个范围比子树的数组区间向左多包含一个位置。标程中，`Prefix` 保存 $b$ 的前缀和，`MinPrefix` 和 `MaxPrefix` 保存上述前缀和极值，均不是序列 $a$ 的最小值或最大值。

左子树的数组区间为 $[L,i-1]$ ，保存的前缀和下标恰好覆盖 $[L-1,i-1]$ ；右子树同理，提供 $[i,R]$ 内的前缀和极值。若某侧没有孩子，就分别使用单值 $P_{i-1}$ 或 $P_i$ . 因此，在孩子算完后，只需常数时间就能计算当前节点的候选答案。再对左右两侧的最小值取较小者、最大值取较大者，即得到当前子树的摘要。

## 正确性

笛卡尔树把所有非空区间分配给一个位于该区间内的最小值节点。固定节点后，左右端点的可选范围彼此独立，前缀和极值公式给出最大的或最小的区间和；根据 $a_i$ 的正负选择相应极值，得到归到该节点的最大乘积。对全部节点取最大值，因此得到全局最优值。

答案初始化为 64 位整数的最小值，不能初始化为 $0$ ，因为空区间不允许，而所有非空区间的答案可能为负。

## 复杂度

单调栈建树、迭代遍历及逆序计算均为 $O(n)$ 时间，空间为 $O(n)$ . 不用递归，单调数组和全相等数组形成的百万节点长链也能处理。

前缀和绝对值不超过 $10^{12}$ ，候选乘积绝对值不超过 $10^{18}$ . 前缀和与乘积均使用有符号 64 位整数，并在乘法前完成类型提升。