饼干交换大会题解¶
解法比较¶
标程采用三字段摘要。出题人的四字段摘要与三字段摘要分别需要 32 和 24 字节的 64 位数值载荷，后者减少 25%；这里不含容器和分配器开销。
出题人解法的线段树为区间保存供给总量、需求总量，以及内部尽量交换后尚未匹配的供给和需求。合并时先让左侧剩余供给满足右侧需求，再做相反方向；若供需仍留在同一侧，则撤回另一侧部分内部交换，改为两次跨侧交换。左右参与者不同，跨侧交换合法；这种重配正是增广匹配，直到无法增加已满足需求。查询按同一方式合并摘要，以总需求减剩余需求得到答案。
Codex（GPT-6）采用的实现使用下文证明的闭式瓶颈公式，只维护供给总量、需求总量和最大的单点供需之和。出题人解法的增广过程与闭式公式求的是同一个最大交换量；公式及割的论证也解释了四字段摘要为何只需记录剩余总量。两者建树为 \(O(n)\) 、单点修改和区间查询为 \(O(\log n)\) ，空间为 \(O(n)\) .Codex 实现的优势是合并只需求和与最大值，省去重配分支；这是摘要与证明的简化，没有渐进提速结论。
一个区间只需三个量¶
对当前询问的参与者，记
其中 \(\mathrm{Demand}\) 为区间内所有人的接收上限总和，\(\mathrm{Supply}\) 为提供上限总和；\(\mathrm{MaxPair}\) 先将每个人的两项上限相加，再在这些和中取最大值。这三个名称也对应标程 FSummary 中的三个成员。
答案为
前两个上限显然分别来自总接收能力和总供给。第三个上限体现了不能自己供给自己：固定参与者 \(i\) ，所有交付都必须使用其他人的供给，或使用其他人的接收能力，所以总量不超过 \((\mathrm{Supply}-s_i)+(\mathrm{Demand}-d_i)\) . 对 \(i\) 取最紧的上限就得到 \(\mathrm{Demand}+\mathrm{Supply}-\mathrm{MaxPair}\) .
为什么最紧的上限可以达到¶
建立一个只用于证明的流网络：源点向每个供给节点 \(i\) 连容量 \(s_i\) 的边；每个接收节点 \(j\) 向汇点连容量 \(d_j\) 的边；供给节点 \(i\) 向所有 \(j\ne i\) 的接收节点连无限容量的边。整数最大流恰好对应可行交付。
考察有限容量割，设留在源点一侧的供给节点集合为 \(A\) . 与这些供给节点相邻的接收节点也必须在源点一侧，否则会割断无限容量边。其余接收节点放在汇点一侧不会增加割容量。因此，固定 \(A\) 后，总可以这样放置接收节点来取得最小割容量。
- \(A\) 为空时，割容量为 \(\mathrm{Supply}\) .
- \(A=\{i\}\) 时，所有接收节点除 \(i\) 外均须在源点一侧，割容量为 \(\mathrm{Supply}-s_i+\mathrm{Demand}-d_i\) .
- \(|A|\ge2\) 时，每个接收节点都能由 \(A\) 中某个不同编号的供给节点到达。因此割容量至少为 \(\mathrm{Demand}\) .
另一方面，把所有供给、接收节点放在汇点一侧，就得到容量为 \(\mathrm{Supply}\) 的割；全部放在源点一侧，就得到容量为 \(\mathrm{Demand}\) 的割。只把供给节点 \(i\) 及其相邻的接收节点放在源点一侧，则得到容量为 \(\mathrm{Supply}-s_i+\mathrm{Demand}-d_i\) 的割。
上述分类说明不存在比公式更小的割，而这些构造说明公式中的每一项都能作为某个割的容量。因此最小割恰好等于公式的值，最大流最小割定理保证这一交付总量可以达到。单人区间的第三项为 \(0\) ，公式同样适用。
线段树¶
每个节点维护区间的 \(\mathrm{Demand}\) 、\(\mathrm{Supply}\) 和 \(\mathrm{MaxPair}\) . 合并时，前两项分别求和，第三项取最大值。
修改一个人的某项上限时，更新叶子的对应值及 \(d_i+s_i\) ，再向上合并。询问合并 \([l,r]\) 的摘要，代入公式即可；无需真正构造流网络。空摘要取三个 \(0\) ，由于各数量非负，它是合并的单位元。
复杂度与数值范围¶
建树 \(O(n)\) ，每次修改或查询 \(O(\log n)\) ，总时间 \(O(n+m\log n)\) ，空间 \(O(n)\) . 总量可超过 32 位范围，所有区间摘要使用有符号 64 位整数；\(\mathrm{Demand}+\mathrm{Supply}\le6\times10^{14}\) .