# 最小值加权的区间和：按右端点维护分组

贡献：Codex（GPT-6）将经典单调栈动态规划应用于左端点分组，给出不变量、正确性证明与实现。它与[出题人的负责人区间方案](solution.zh.md)具有相同的线性复杂度，作为并列解法。

## 固定右端点

令 $P_r$ 为前 $r$ 项之和。所有以 $r$ 结尾的区间，按最小值分组；组内保存最小值 $m$ 、左端点数量 $c$ ，以及这些左端点之前的前缀和之和

$$S=\sum_{l\text{ in group}}P_{l-1}.$$

该组对当前答案的贡献为 $m(cP_r-S)$ .维护全局量

$$U=\sum_{\text{groups}}mc,\qquad V=\sum_{\text{groups}}mS,$$

则本轮所有区间贡献就是 $P_rU-V$ .

## 单调栈更新

按左端点由小到大的顺序，区间最小值不下降。把最小值相等的连续左端点合为一组，组的最小值严格递增，保存在栈中。

读入 $x=A_r$ 前，已有组对应右端点 $r-1$ .建立新组，初始 $c=1,S=P_{r-1}$ ，代表单点区间。弹出所有最小值 $m\ge x$ 的末尾组：

1. 从 $U,V$ 中删除该组的 $mc,mS$ .
2. 把该组的 $c,S$ 加入新组。

这些组扩展后最小值都变为 $x$ ，其左端点和相应 $P_{l-1}$ 不变。未弹出的组保持原最小值。压入合并后的新组，更新 $U,V$ ，再令 $P_r=P_{r-1}+x$ ，将 $P_rU-V$ 加入总答案。

## 正确性

归纳假设栈准确划分所有以 $r-1$ 结尾的区间。扩展到 $r$ 后，每个最小值变为 $\min(m,x)$ .单调性保证所有需要变为 $x$ 的组恰好是栈的一个后缀，正是被合并的组；单点区间也归入最小值为 $x$ 的新组。因此更新后的栈恰好划分所有以 $r$ 结尾的区间，并保持各组的 $c,S$ .公式 $m(cP_r-S)$ 精确汇总组内区间贡献，故每轮得到全部当前右端点的贡献。每个区间只有一个右端点，总累加正确。

## 数值、复杂度与用途

每组只入栈、出栈一次，总时间 $O(N)$ ，栈空间 $O(N)$ .一个栈项保存两个三十二位整数及一个十六字节宽整数，共二十四字节。前缀和 $P_r$ 与 $U$ 的绝对值不超过 $10^{16}$ ，用六十四位；$S,V$ 、乘积 $P_rU$ 和答案用主解所述的可移植一百二十八位类型。$P_rU$ 的绝对值至多 $10^{32}$ ，远小于宽整数上界；总答案采用主解的完整区间绝对值界。

数据可以流式读入。最大栈仍可有 $N$ 项，所以它不承诺次线性最坏空间。本机正式输入中该方案运行更快，最大工作集与负责人方案接近；实测不能替代对所有平台的重新校准。两份程序均通过完整范围、独立区间枚举、最大规模子树聚合与宽整数专项核对。

程序：[alternative.cpp](alternative.cpp)。[完整测量](../../../docs/benchmark-R26.json)。