短板翻盘题解¶
解法比较¶
出题人解法先用单调栈确定每个 \(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\) 时：
- 只要栈顶的值大于 \(a_i\) ，就将它弹出。最后弹出的节点成为 \(i\) 的左孩子；若没有弹出节点，则左孩子为空。
- 若栈仍非空，将 \(i\) 设为新栈顶节点的右孩子。
- 将 \(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}\) ，其中两个下标可以独立选择：
- 若 \(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 位整数，并在乘法前完成类型提升。