# 饼干交换大会题解

## 解法比较

标程采用三字段摘要。出题人的四字段摘要与三字段摘要分别需要 32 和 24 字节的 64 位数值载荷，后者减少 25%；这里不含容器和分配器开销。

出题人解法的线段树为区间保存供给总量、需求总量，以及内部尽量交换后尚未匹配的供给和需求。合并时先让左侧剩余供给满足右侧需求，再做相反方向；若供需仍留在同一侧，则撤回另一侧部分内部交换，改为两次跨侧交换。左右参与者不同，跨侧交换合法；这种重配正是增广匹配，直到无法增加已满足需求。查询按同一方式合并摘要，以总需求减剩余需求得到答案。

Codex（GPT-6）采用的实现使用下文证明的闭式瓶颈公式，只维护供给总量、需求总量和最大的单点供需之和。出题人解法的增广过程与闭式公式求的是同一个最大交换量；公式及割的论证也解释了四字段摘要为何只需记录剩余总量。两者建树为 $O(n)$ 、单点修改和区间查询为 $O(\log n)$ ，空间为 $O(n)$ .Codex 实现的优势是合并只需求和与最大值，省去重配分支；这是摘要与证明的简化，没有渐进提速结论。

## 一个区间只需三个量

对当前询问的参与者，记

$$\mathrm{Demand}=\sum_i d_i,\qquad \mathrm{Supply}=\sum_i s_i,\qquad \mathrm{MaxPair}=\max_i(d_i+s_i)$$

其中 $\mathrm{Demand}$ 为区间内所有人的接收上限总和，$\mathrm{Supply}$ 为提供上限总和；$\mathrm{MaxPair}$ 先将每个人的两项上限相加，再在这些和中取最大值。这三个名称也对应标程 `FSummary` 中的三个成员。

答案为

$$\min(\mathrm{Demand},\ \mathrm{Supply},\ \mathrm{Demand}+\mathrm{Supply}-\mathrm{MaxPair})$$

前两个上限显然分别来自总接收能力和总供给。第三个上限体现了不能自己供给自己：固定参与者 $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}$ .