# 直线上的容量运输：分块补充方案

## 方法、来源与定位

沿用[首选题解](solution.zh.md)的出题人残量运输模型及最近空位选择，Codex（GPT-6）实现排序分块。最优性证明和边际费用公式与首选方案共用。本文件完整说明替代的区间数据结构；[程序](alternative-blocks.cpp)支持全部正式范围。

## 块内表示

将 $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\left(n\log B+m\left(\log n+\frac nB\log B+B\log B\right)\right),
$$
空间为 $O(n)$ .实际程序使用 $B=320$ ，与正式最大规模的平方根接近；上式明确保留块长参数。若按输入规模选择 $B=\lceil\sqrt n\rceil$ ，便得到通常的平方根分块界。

其每次操作的上界不依赖流量符号跨零的次数，且实测内存较小；代价是要扫描多个块并排序。两份程序都应通过完整范围。时限依据[测量结果](../../../docs/benchmark-R28.json)覆盖较慢者，并不声称分块在每种输入上都更快。