直线上的容量运输：分块补充方案¶
方法、来源与定位¶
沿用首选题解的出题人残量运输模型及最近空位选择，Codex（GPT-6）实现排序分块。最优性证明和边际费用公式与首选方案共用。本文件完整说明替代的区间数据结构；程序支持全部正式范围。
块内表示¶
将 \(n\) 条边分成长度至多 \(B\) 的连续块。每块保存每条边的原始流量 \(a_i\) 、一个统一偏移量 \(t\) ，使真实流量为 \(a_i+t\) ；再把块内 \((a_i,d_i)\) 按原始流量排序，建立距离 \(d_i\) 的前缀和。流量相同的边可以按距离打破平局，前缀查询仍按流量阈值整体取值。
完整块向右的边际费用是总距离减去两倍“真实流量小于零”的距离和。用二分查找 \(a_i<-t\) 的边即可。向左的费用是两倍“真实流量不大于零”的距离和减去总距离，对应阈值 \(a_i\le-t\) .部分块直接逐条边计算。
区间流量加一或减一时，完整块只修改统一偏移；最多两个部分块逐项修改原始流量，然后重新排序并建立前缀和。偏移量可以保留，不必先下推，因为修改原始值与修改真实值具有相同增量。
正确性与完整算法¶
排序只改变查询顺序，不改变每条边的流量和距离对应关系。完整块的二分前缀和恰好选择负流量或非正流量的边，所以得到与逐边绝对值差相同的残量费用。完整块偏移与部分块修改也都恰好实现区间统一加减。因此这些操作可以直接替换首选模型中的线段树操作。
仍用有序集合找两侧最近空位，选择最小残量费用的方向并更新流量、目的地容量和答案。首选题解的逐次最小费用增广证明随之适用。
复杂度与比较¶
初始化为 \(O(n\log B)\) .每次查询扫描至多 \(O(n/B)\) 个完整块并二分，另直接处理 \(O(B)\) 条边；更新最多重排两个部分块。因此总时间为
空间为 \(O(n)\) .实际程序使用 \(B=320\) ，与正式最大规模的平方根接近；上式明确保留块长参数。若按输入规模选择 \(B=\lceil\sqrt n\rceil\) ，便得到通常的平方根分块界。
其每次操作的上界不依赖流量符号跨零的次数，且实测内存较小；代价是要扫描多个块并排序。两份程序都应通过完整范围。时限依据测量结果覆盖较慢者，并不声称分块在每种输入上都更快。