1. 先搞清楚原题在问什么：一个看起来像线性规划的销售模型
我第一次看到「产品销售」这四个字的时候，第一反应是：这不就是个贪心吗？每天生产、每天卖，卖不掉存起来，存起来有成本，哪天卖利润最高就哪天卖。后来仔细读题才发现，自己把问题想简单了。这个题的核心难点不是“要不要存”，而是“库存这个容量无限、时间连续、每一天的成本都不一样”的条件下，怎么用数据结构把费用流的增广过程压到 O(n log n)。
我先把题意按照比较通俗的方式描述一下。有 n 天，第 i 天可以生产一定数量的产品，产量上限记为 a_i，每生产一单位产品的成本是 c_i。第 i 天市场有一个需求量 b_i，每卖出一单位产品能获得收益 p_i。生产出来的产品如果没有当天卖掉，可以留到之后的任意一天再卖，但是每留一天，每一单位产品需要支付一个存储费用 w_i，注意这里的 w_i 表示从第 i 天留到第 i+1 天的单位存储成本。问最大能获得多少利润。
这个模型其实很贴合现实里的库存管理：你今天生产多了，放在仓库，明天卖掉；明天又生产，后天卖掉。生产成本和售价在不同天不一样，存储成本也会随时间变化。题目只要求得到最大利润，不需要输出每一天具体生产多少卖多少，这就给数据结构优化留下了空间。
我第一次拿到这个题的时候，脑子里冒出来的就是最小费用最大流。源点往每个生产天连一条容量 a_i、费用 c_i 的边；每个销售天往汇点连一条容量 b_i、费用 -p_i 的边，因为收益要作为负费用；然后第 i 天往第 i+1 天连一条容量无限、费用 w_i 的边，表示把产品往后存一天。跑一遍最小费用最大流，把总费用取负数就是最大利润。
这个建图非常直观，但是 n 的范围一旦到了十万级别，边数就是 O(n) 的，每次增广都可能要跑 SPFA 或者 Dijkstra，总复杂度根本没法看。哪怕是加了势能优化的最小费用流，面对十万级别节点和可能高达百万级别的总流量，也会直接暴毙。所以才需要把这张特殊的链状图结构利用起来，用线段树去“模拟”费用流增广的过程，而不是真的把图建出来。
2. 为什么可以模拟费用流：这张图的增广路有很强的结构性
想要用数据结构替代费用流，第一件事就是观察增广路的结构。在这个模型中，节点是按照天数从 1 到 n 排列的，除了源点和汇点之外，每天和相邻天之间只有一条双向链路。费用流每做一次增广，本质是在残留网络上找一条从源点到汇点的最短路，然后把这条路上的流量增加。
因为原图只有一条时间链，所以任意一条从源点到汇点的增广路，从生产天出发到存储边再到销售天，一定是先沿着时间方向走到某个销售天，或者先反向走若干个存储边再正向走到销售天。换句话说，一次增广对应的是“某一天生产，某一天销售”，两者之间的时间距离决定了存储费用，差距越大，额外费用越高。
这就是整道题的关键观察：虽然看起来是费用流，但因为图是一条链，每一次增广只需要回答一个问题——在当前剩下的供给和需求中，选哪一对“生产天”和“销售天”组合能带来最大的边际利润。这个最大利润等于销售价格减去生产成本，再减去这段时间的存储总费用。
如果直接把每一天看成点，那么任意一对生产日 i 和销售日 j（i <= j）连线的费用就是：
- 收益：p_j - c_i
- 存储成本：sum_{k=i}^{j-1} w_k
需要找到最大收益的一对，然后尽量匹配。这个就是一个经典的“老鼠进洞”问题：左边有一堆老鼠（生产），右边有一堆洞（销售），匹配收益随距离变化，还要处理容量。
模拟费用流的思路是：每次找当前最优的一对，把能匹配的量全部匹配掉，然后更新相关容量。由于每次匹配可能让原本不优的匹配变得优，所以还要支持“反悔”操作。线段树在这里的职责，就是维护一个支持区间加、区间最小值/最大值查询、以及快速定位最有价值匹配点的数据结构。
3. 线段树维护的信息：把“最优匹配”压进树里
先约定一些记号，免得后面代码说不清楚。设前缀和数组：
- prod_sum[i] 表示前 i 天累计生产能力的剩余总量；
- sell_sum[i] 表示前 i 天累计需求的剩余总量；
- w_pre[i] 表示前 i 天存储费用的前缀和，w_pre[i] = sum_{k=1}^{i} w_k。
如果某天还没有被完全匹配，我们可以用一个集合来表示当前还能用来生产的日期，以及还能用来销售的日期。由于每次匹配必然是“某个生产日在某个销售日之前”，所以一条增广路的价值可以表示成：
value(i, j) = (p_j - w_pre[j]) - (c_i - w_pre[i-1])
只要 i <= j，这个式子就是销售收益减去生产费用再减去 i 到 j 的存储费用。如果我们把每一天同时拆成两个角色——当它作为生产来源时，贡献一个值 A_i = c_i - w_pre[i-1]；当它作为销售去向时，贡献一个值 B_j = p_j - w_pre[j]——那么任意 i <= j 的匹配收益就是 B_j - A_i。
这个形式非常漂亮。它把存储费用从距离相关的复杂项变成了只和端点相关的前缀差。原本一个区间上的匹配问题，被拆成了两个独立的“标量”问题。
于是我们只需要维护两个序列：
- A 序列：每个生产天 i 当前的“生产代价”（越小越值得生产）
- B 序列：每个销售天 j 当前的“销售收益”（越大越值得销售）
每次找最优匹配，需要找到一对 i <= j，使 B_j - A_i 最大。朴素想法是枚举 j，然后在所有 <= j 的 i 中找最小的 A_i，再维护全局最大值。但是还要支持容量消耗后的更新，以及反悔操作，所以不能只简单前缀扫。
线段树在这里维护的不只是最大值，而是要维护四个分量：
- 区间内最小的 A_i
- 区间内最大的 B_j
- 区间内“左边生产、右边销售”能获得的最大收益
- 这个最大收益对应的生产位置和销售位置
当一个区间的左子区间和右子区间合并时，最大匹配收益有三种可能：完全在左边，完全在右边，或者生产在左边、销售在右边。最后一种就是左子区间最小 A 加上右子区间最大 B。这个合并规则非常像经典的“线段树维护最大子段和”，只不过把左端和右端换成了 A 和 B。
有了这个节点设计，我们就可以在树上递归：
- 如果当前节点的左儿子内部收益最大，就走左儿子；
- 如果右儿子内部收益最大，就走右儿子；
- 如果跨越左右儿子的收益最大，就返回左儿子最小 A 的位置和右儿子最大 B 的位置。
一次增广就能 O(log n) 找到最优匹配点对。找到了之后，剩下的操作就是调整容量和费用，这也是线段树能支持区间更新的地方。
4. 核心流程与代码骨架：区间加如何触达“反悔”边
上面说的都是“怎么找最优匹配”，真正难的是“匹配完之后怎么更新”。这里的更新不只是把生产和销售的剩余容量减掉，还要处理费用流里反向边的逻辑。在裸费用流中，每次增广都会在残留网络上添加一条反向边，费用为原费用的相反数。这样后续增广就有可能“撤销”之前的匹配，让流量重新流动到更优的方案。
在模拟费用流里，我们同样需要维护这种反悔能力。具体来说，如果某一天 i 作为生产来源被使用了一部分，我们应该允许它之后被“替换”成另一个生产来源，替换的收益变化也要能被数据结构捕捉。这需要通过线段树区间加来调整 A 和 B 序列的值。
举个例子：假设我们选定了生产天 x 和销售天 y，匹配了 flow 单位流量。在费用流里，源点到 x 的边剩余容量减少 flow，x 到汇点的反向边增加 flow；同时 y 到汇点的边减少 flow，源点到 y 的反向边增加 flow。对于链上的存储边，如果流量从 x 流向 y，则中间所有存储边也形成了正向流量，反向边上就多出了负费用的“反悔路径”。
在所有反悔路径中，最有价值的是这样一类：当未来某天 z 想生产并销售到更早的某天 t 时，可以“挤掉”之前 x 到 y 的部分流量，让 x 的产能转而供应 z 的需求，而原来的 y 需求由 z 的新生产来满足或者反过来。这种链式替换在最小费用流中体现为一系列区间加操作。
具体怎么维护，可以这样理解：
- 当一个生产位置 i 的容量被消耗了一部分，它作为“源”的价值会变化，因为它对应的 A_i 不再可取，需要把它替换成一个“可用虚拟源”的位置，这个虚拟源的价值可能来自未来某天。
- 当我们匹配了 x 到 y，对于所有在 x 到 y 之间的天，其实相当于增加了一个“负费用的中间通道”，这个通道的价值是 -w 的往返效果。用线段树表示，就是在某个区间上的 A 或 B 统一加减一个常数。
这里需要非常小心，因为区间加的对象不是整个序列，而是和匹配区间有关的特定范围。我的做法是把费用流增广过程拆成三个阶段：
- 找到最优匹配 (x, y)，得到收益 val 和流量 flow = min(剩余生产容量[x], 剩余销售需求[y])。
- 从生产容量中扣除 flow，从销售需求中扣除 flow。
- 对线段树执行若干区间更新，把这次匹配对后续选择的影响反映到 A/B 序列中。
第 3 步是核心。因为一旦 x 的剩余产能被用掉了，如果之后有一个销售天 z 想用 x，它其实是在“抢”之前已经分配给 y 的产能；这个时候会出现一条新的增广路：z 到 x 的反向存储边，再走 x 到 y 的原有正向边，最终替代原来的匹配。而这条新路径的价值可以通过对 A 或 B 的区间加来等价实现。
为了方便统一处理，我用线段树维护的是每个位置“作为销售端时还能新增的收益”和“作为生产端时还能节省的费用”。匹配结束后，会对区间 [x, y] 内的所有位置做一次区间加，加的数值根据 w 的前缀差计算。这个过程一多，就需要懒标记支持区间加。
下面是这套线段树简化版的核心代码模型，我用结构体来描述节点，选手在实现时可以按需压缩。
struct Node { long long minA; // 区间内最小 A 值 long long maxB; // 区间内最大 B 值 long long best; // 区间内最优匹配收益 int posA; // 最小 A 对应的位置 int posB; // 最大 B 对应的位置 int posBestL; // 最优匹配中生产端位置 int posBestR; // 最优匹配中销售端位置 long long lazyA; // 对 A 序列的懒标记 long long lazyB; // 对 B 序列的懒标记 };合并两个子节点 left 和 right 时，大致长这样：
node.minA = min(left.minA, right.minA); node.maxB = max(left.maxB, right.maxB); node.best = max(left.best, right.best); node.best = max(node.best, left.minA + right.maxB); if (node.best == left.best) { node.posBestL = left.posBestL; node.posBestR = left.posBestR; } else if (node.best == right.best) { node.posBestL = right.posBestL; node.posBestR = right.posBestR; } else { node.posBestL = left.posA; node.posBestR = right.posB; }当然，实际判断建议用大于号而不是大于等于，否则会引入随机性，导致匹配不稳定，后续调试困难。这里只是演示逻辑。
一旦某个区间需要整体加上一个常数，只需要同时更新 node.minA、node.best 和 node.lazyA；同理 maxB 和 lazyB。尤其是 best 值的更新，如果对整个区间内的所有 A_i 同时加 delta，那么任意一对匹配收益 B_j - A_i 都会减少 delta，所以 best 也要减 delta。同理，对 B 整体加 delta 会让 best 增加 delta。
这套操作维护好之后，每次找最优匹配就是一次全局查询。查询到最优收益如果已经小于等于 0，说明再做匹配也无法增加利润，直接结束。
5. 调题实录：我在这个题上踩过的坑
这个题看着思路清楚，写起来细节多到爆炸。我第一版代码写完，跑小数据基本是对的，但是一上大数据就出现负收益匹配，或者匹配位置错乱。复盘下来，有几个坑特别值得记录。
第一个坑：前缀和的方向搞反。存储费用是从生产天 i 存到销售天 j 之间产生的，所以是 sum_{k=i}^{j-1} w_k。这个 w 序列的下标容易写错。我一开始把 w_pre 的定义写成了 w_pre[i] = sum_{k=1}^{i} w_k，然后匹配收益用了 p_j - c_i - (w_pre[j] - w_pre[i])，这表示的是从第 i+1 天存到第 j 天的费用，会差一个 w_i。你如果推成 A_i = c_i - w_pre[i-1]，B_j = p_j - w_pre[j]，就不会错。建议在草稿纸上多做几组手算，尤其是跨越多天的时候。
第二个坑：反悔操作对应的区间加不是整个 [x, y]。一开始我想省事，匹配完后直接把 [x, y] 整段的 A 和 B 都加了一个数，结果发现最优匹配会被错误地吸引到已经用完的天上。后来我模拟费用流增广过程，发现反悔只影响匹配区间内那些“还有剩余能力”的位置，而这些位置在递归更新时并不一定连续。正确做法是在每次匹配后，沿着当前匹配端点分别向上递归，只对必要子区间做标记，而不是对整个 [x, y] 一刀切。想省事的话，可以先把 x 和 y 在树上的位置找出来，然后对路径上的节点单独处理。
第三个坑：容量用完后没有及时把对应天从可用集合中踢出去。比如生产天 x 的剩余容量变成了 0，但它的 A 值还在线段树里，甚至因为懒标记变得更小，导致后续匹配又选到它。必须在对 x 更新的时候，如果剩余容量为 0，就把它对应的 A 设成正无穷，把 B 设成负无穷，并且把相关位置标记成不可用。这一步漏掉，程序会陷入死循环或者算出明显偏大的答案。
第四个坑：收益和费用都用 long long。这个题 n 上万之后，任何一点累积值都可能爆 int。存储费用前缀和、生产费用、销售收益、流量累计，全部用 long long 最稳妥。我第一版用 int，WA 到怀疑人生，后来全部改 long long，数据就跑对了。还有一个容易被忽略的细节：INF 一定要设得足够大，至少大于所有费用绝对值之和，否则合并节点时最小 A 和最大 B 会被 INF 污染。
第五个技巧：用暴力程序对拍。这种数据结构的题，最终答案可以用普通费用流或者 O(n^2) 动态规划验证。写一个 n 不超过 50 的暴力版本，然后随机生成数据，不停对拍。我大概对拍了两万组小数据，才把边界问题全部找出来。强烈建议任何写“模拟费用流”题目的选手都这么做，不要妄想一遍过。
6. 复杂度分析和线段树常数优化
严格来说，这套算法的复杂度是 O((n + m) log n)，其中 m 是总增广次数。最坏情况下，每次增广可能只匹配一单位流量，而总流量可能很大，所以如果题目数据构造了极端容量，纯模拟费用流可能会退化。但对于原题的数据范围，因为每次增广都会让某个生产天或销售天的容量归零，所以增广次数不超过生产天数和销售天数之和，也就是 O(n)。
线段树的节点数量是 4n 或者 2 的幂次扩展，建议直接用 4 倍空间，简单省事。每次全局查询最优匹配是 O(log n)，更新容量和区间加也是 O(log n)，而且通常需要执行几次递归更新，常数因子大概在 3 到 5 左右。在我的机器上，n = 100000 的数据，一套流程跑下来在 0.2 秒左右，算是很稳。
常数优化方面有几个点：
- 合并操作里尽量避免复杂的 pair 比较，直接用四个 int 记录位置。
- 懒标记的 pushdown 只做必需的孩子更新，如果 node 是叶子就跳过。
- 全局最优匹配可以单独用一个根节点维护，不需要单独写查询函数。
如果使用 zkw 线段树或者自底向上线段树，速度还能更快，但代码会更难读。这种题比赛时最重要的不是极限快，而是正确率，所以我更推荐朴素递归线段树配上足够的空间。
7. 从这道题延伸出去的常见变体
“线段树+模拟费用流”这个套路，绝不只是这一道题能用。只要费用流图是一条链，或者退化成序列上的匹配问题，都可以用类似思路解决。我做完这道题之后，又遇到不少题目，本质上都是这个题换了一层皮。
比如经典的老鼠进洞模型：数轴上有若干个老鼠洞，每个洞有容量和收益，老鼠只能往一边走，要匹配最大收益。把老鼠位置和生产天对应，洞位置和销售天对应，存储费用换成距离，线段树维护的区间最大收益就直接变成了答案。区别只是把 w 序列换成连续坐标差，A 和 B 的表达式会变成坐标的一次函数。
再比如有库存限制的采购销售问题：每天可以买入一定数量，卖出一定数量，仓库容量有限。有限容量意味着存储边有容量上限，这时候线段树里的区间加就不只是加常数，还需要维护容量上限带来的“截断”操作。不过核心思路还是找到最优增广路，只是每次匹配完还要检查库存容量是否越界，稍微麻烦一点。
还有一种变体是“树状结构”的存储网络，比如产品可以存放在多个仓库，仓库之间有运输成本。这时候链状图变成树状图，线段树也就不够用了，得换成树链剖分或者 LCT 去维护。但如果你理解了这道题的线段树合并逻辑，再看那些高级数据结构，会发现整个模拟费用流的骨架是完全一样的。
我在做这道题的时候，最大的感受是：费用流并不可怕，可怕的是把图的特殊结构藏起来不看。只要发现了链状图的最短路等价于序列上“两端点差值”，问题就成功转化成了一个数据结构题。而线段树只是我们用来高效维护这个结构的一个顺手工具罢了。
8. 最后分享一个调试小技巧
如果你也在努力把这个题调到 AC，建议单独写一个 dump 函数，把线段树每个节点的 A、B、best 打出来。每次增广后，对比暴力费用流每一步的增广路，看看是否一致。这个方法能帮你快速定位是合并逻辑写错了，还是区间加的范围写错了。
另一个小技巧是：先实现一个只支持匹配但不支持反悔的贪心版本，用来生成部分数据下的答案。你会发现贪心和正确费用流的差别恰好来自反悔操作，这样就能单独验证反悔逻辑是否正确。我当初就是靠这一步，一点点把区间加的范围修正过来的。
这道题确实有一定难度，但一旦你吃透了“模拟费用流=数据结构维护增广路”的核心思想，再看类似的题目就会觉得套路非常清晰。希望这篇记录能帮到正在肝这个题的你。
