CF1919F2 Wine Factory (Hard Version)

题意

有 \(n\) 个桶，每个桶里有 \(a_i\) 单位水。

每次查询按 \(1,2...,n\) 的顺序进行。

当操作到桶 \(i\) 时，先将当前桶里的水取 \(b_i\) 加入答案。

并将当前里的水全部流向 \(i + 1\)，最多只能流 \(c_i\) 单位。

每次修改 \(a_p, b_p, c_p\) 查询答案。

Sol

不难想到建模网络流。

• \(S \to i\)，容量 \(a_i\)
• \(i \to i + 1\)，容量 \(c_i\)
• \(i \to T\)，容量 \(b_i\)

套路地，考虑最大流模型转最小割。

注意到对于 \(i = j + 1\)，如果割了 \(i \to T\) 和 \(S \to j\) 就要加上当前 \(c_i\) 的贡献。

直接线段树区间合并单点修改做完了。