题解

思路

总水量 $s=c+d$ 在所有操作中保持不变。固定 $s$ 后，第一个水箱水量的合法区间为

$$L_0=\max(0,s-b),\quad R_0=\min(a,s).$$

一次正操作把当前水量 $x$ 变为 $\max(L_0,x-v_i)$；一次负操作把它变为 $\min(R_0,x-v_i)$。因此，所有操作的复合映射始终可以写成

$$F(x)=\operatorname{clamp}(x+q,L,R).$$

做法

子任务 1

枚举全部 $(c,d)$，逐次模拟操作，复杂度 $O(nab)$。

子任务 2

固定总水量后，$F(x)$ 是“常数、斜率一、常数”的单调函数。用逐状态模拟作为查询，二分第一个大于左端答案的位置和第一个等于右端答案的位置，再线性填写这一条对角线。复杂度 $O(n(a+b)\log\min(a,b)+ab)$。

满分算法

对每个总水量维护三元组 $(q,L,R)$，初始为 $(0,L_0,R_0)$。若 $v_i>0$：

$$q\leftarrow q-v_i,\quad L\leftarrow\max(L_0,L-v_i),\quad R\leftarrow\max(L_0,R-v_i).$$

若 $v_i<0$：

$$q\leftarrow q-v_i,\quad L\leftarrow\min(R_0,L-v_i),\quad R\leftarrow\min(R_0,R-v_i).$$

处理完后，对该对角线每个初始 $c$ 输出 $\operatorname{clamp}(c+q,L,R)$。

另一种等价实现维护斜率为一的初始区间左右端点，并先模拟左端点最终值。

正确性证明

固定总水量时，水箱容量限制恰好等价于把第一个水箱水量限制在 $[L_0,R_0]$。每次倒水是一次平移后向左端或右端截断。对夹逼线性函数再做平移与单侧截断，仍是夹逼线性函数，且上述转移直接给出了新参数。归纳可知最终三元组表示全部操作的精确复合映射，因此填写的每个矩阵元素都正确。

复杂度

满分算法对每个总水量扫描一次操作序列，再输出整个矩阵，时间复杂度 $O(n(a+b)+ab)$，空间复杂度 $O(ab)$。