题目大意

有 $n$ 个水塔，第 $i$ 个水塔初始水量为 $a_i$，前方巫师的能力为 $b_i$。相邻水塔 $i$ 与 $i+1$ 之间有一根容量为 $c_i$ 的管道。处理过程按 $i=1$ 到 $n$ 顺序进行：巫师 $i$ 从当前塔中取走至多 $b_i$ 的水变成酒；剩余的净水至多 $c_i$ 流入下一塔。有 $q$ 次修改，每次修改一个 $p$ 对应的 $a_p, b_p, c_p$，求每次修改后的总产酒量。

---

网络流建模

建立一个流网络，顶点共 $n+2$ 个：源点 $s = n+1$，汇点 $t = n+2$，以及 $n$ 个代表水塔的点。

• 对每个 $i$，添加边 $s \to i$，容量为 $a_i$（原始水量）；
• 对每个 $i$，添加边 $i \to t$，容量为 $b_i$（巫师转化能力）；
• 对每个 $1 \le i \le n-1$，添加边 $i \to i+1$，容量为 $c_i$（管道容量）。

从 $s$ 到 $t$ 的最大流就是原问题的产酒总量。由最大流最小割定理，我们可以改为求该网络的最小割。

---

最小割与状态选择

考虑任一个 $s$-$t$ 割。对于每个 $i$，必然要割掉 $s \to i$ 或 $i \to t$ 中的至少一条，否则存在路径 $s \to i \to t$ 使 $s$ 与 $t$ 连通。可以证明：最小割中恰好包含这两条边中的一条。

证明：若一个割同时包含 $s \to i$ 和 $i \to t$，我们分两种情况：

1. $s$ 能到达 $i$：此时去掉 $s \to i$ 不影响 $s$ 到达 $i$ 的能力，去掉后割的容量不会变大。
2. $s$ 不能到达 $i$：此时去掉 $i \to t$ 不会使 $s$ 到达 $t$，割的容量同样不会变大。 因此总可以去掉其中一条边而得到费用不超过原割的新割，故最小割中不会同时包含两者。

于是每个 $i$ 的选择构成一个二选一：割 $s \to i$（代价 $a_i$），称为状态 $A$；或割 $i \to t$（代价 $b_i$），称为状态 $B$。

设每个位置的选择用 $x_i \in \{A, B\}$ 表示。注意当出现 $x_i = B$ 且 $x_{i+1} = A$ 时，$s$ 可以通过 $s \to i$（未割）、管道 $i \to i+1$（未割）以及 $i+1 \to t$（未割）到达 $t$，因此为了切断这条路径，必须额外割掉边 $i \to i+1$，付出代价 $c_i$。

问题转化为：为每个 $i$ 选择 $A$ 或 $B$，最小化

$$\sum_{i: x_i = A} a_i + \sum_{i: x_i = B} b_i + \sum_{i: x_i = B,\; x_{i+1} = A} c_i $$

---

动态规划

令 $dp[i][0]$ 表示前 $i$ 个位置，且第 $i$ 个选择 $A$ 的最小代价；
$dp[i][1]$ 表示前 $i$ 个位置，且第 $i$ 个选择 $B$ 的最小代价。

转移时考虑相邻状态产生的额外管道代价：

• 若当前选 $A$：前一个是 $A$ 无额外代价，前一个是 $B$ 需额外 $c_{i-1}$。
• 若当前选 $B$：无论前一个是 $A$ 还是 $B$，都不会触发 $BA$ 模式，无额外代价。

转移方程如下：

$$\begin{aligned} dp[i][0] &= a_i + \min\big(dp[i-1][0],\; dp[i-1][1] + c_{i-1}\big) \\ dp[i][1] &= b_i + \min\big(dp[i-1][0],\; dp[i-1][1]\big) \end{aligned} $$

初始条件：$dp[1][0] = a_1,\; dp[1][1] = b_1$。 最终答案即为 $\min(dp[n][0],\, dp[n][1])$。

---

线段树优化

为了支持单点修改，使用线段树维护上述 DP 的区间合并。
线段树的每个节点表示一个区间 $[l, r]$，存储一个 $2 \times 2$ 的矩阵 $M$，其中 $M[x][y]$ 表示区间左端点状态为 $x$、右端点状态为 $y$ 时，该区间内部的最小代价（包含区间内所有 $a_i, b_i$ 以及内部相邻位置之间的 $c_k$）。

叶节点（区间长度为 $1$）：

• $M[0][0] = a_i$ （全 $A$）
• $M[1][1] = b_i$ （全 $B$）
• 其余 $M[0][1], M[1][0]$ 设为充分大的数（表示非法状态，因为单点区间左右端点必须相同）。

合并操作：将左儿子 $L$（区间 $[l, mid]$）和右儿子 $R$（区间 $[mid+1, r]$）合并为父亲 $U$。
枚举左儿子的右端点状态 $p$ 和右儿子的左端点状态 $q$，当 $p = B$ 且 $q = A$ 时，需要额外加上边 $mid \to mid+1$ 的容量 $c_{mid}$。合并公式为：

$$U[x][y] = \min_{p,q \in \{0,1\}} \Big( L[x][p] + R[q][y] + (p=1 \land q=0 \;?\; c_{mid} : 0) \Big) $$

即：

$$U[x][y] = \min\begin{cases} L[x][0] + R[0][y] \\ L[x][1] + R[1][y] \\ L[x][0] + R[1][y] \\ L[x][1] + R[0][y] + c_{mid} \end{cases} $$

建树时自底向上合并，每次更新只需修改叶节点并向上更新路径，单次操作 $O(\log n)$。

最终答案取根节点四个状态的最小值：

$$\text{ans} = \min\big(U[0][0],\, U[0][1],\, U[1][0],\, U[1][1]\big) $$

总时间复杂度 $O((n+q)\log n)$，空间复杂度 $O(n)$，完全满足本题数据范围。