企业官网建设流程全解析

思路概述

一次操作只是把水从一个箱子倒到另一个箱子，系统总水量保持不变。

因此状态(x,y)(x,y)(x,y)始终位于同一条直线

x+y=s x+y=sx+y=s

上（斜率为−1-1−1）。

原问题可以按总水量sss拆成若干条互不影响的一维问题。

1. 把每条斜线转成一维区间

固定sss时，合法状态满足

0≤x≤a,0≤y≤b,x+y=s 0\le x\le a,\quad 0\le y\le b,\quad x+y=s0≤x≤a,0≤y≤b,x+y=s

等价于

x∈[L,R],L=max⁡(0,s−b), R=min⁡(a,s) x\in[L,R],\quad L=\max(0,s-b),\ R=\min(a,s)x∈[L,R],L=max(0,s−b),R=min(a,s)

令t=x−Lt=x-Lt=x−L，则t∈[0,len]t\in[0,\text{len}]t∈[0,len]，其中len=R−L\text{len}=R-Llen=R−L

也就是说：同一条斜线上的全部初态，等价于一段一维区间

2. 单次操作的几何含义

在固定斜线上看：

• vi>0v_i>0vi​>0（箱 1 倒向箱 2）：xxx减小，对应区间整体左移
• vi<0v_i<0vi​<0（箱 2 倒向箱 1）：xxx增大，对应区间整体右移
• 超出边界[0,len][0,\text{len}][0,len]的部分会被容量限制“压”到端点

所以对一条斜线，只需维护：

• 平移量add\text{add}add
• 最终有效区间[lo,hi][lo,hi][lo,hi]（经过边界挤压后可到达的位置）

顺序处理nnn次操作即可得到该斜线的整体变换，复杂度O(n)O(n)O(n)

3. 从预处理结果还原答案

对每个s∈[0,a+b]s\in[0,a+b]s∈[0,a+b]，预处理参数(L,add,lo,hi)(L,\text{add},lo,hi)(L,add,lo,hi)

对于任意初态(c,d)(c,d)(c,d)：

• 先定位到对应斜线：s=c+ds=c+ds=c+d
• 在线内坐标：t=c−Lt=c-Lt=c−L
• 终态坐标

t′=clamp⁡(t+add, lo, hi) t'=\operatorname{clamp}(t+\text{add},\ lo,\ hi)t′=clamp(t+add,lo,hi)

最终第一个箱子的水量为

x′=L+t′ x'=L+t'x′=L+t′

这正对应“中间按平移，左右被压到边界点”的行为

4. 复杂度

• 斜线数量：a+b+1a+b+1a+b+1
• 每条斜线处理nnn次操作：O(n)O(n)O(n)
• 输出全部(a+1)(b+1)(a+1)(b+1)(a+1)(b+1)个初态答案

总复杂度为

O((a+b+1)⋅n+(a+1)(b+1)), O\big((a+b+1)\cdot n + (a+1)(b+1)\big),O((a+b+1)⋅n+(a+1)(b+1)),