解题思路
每个断面的下界是覆盖它的回灌泵里最大的那个,上界是覆盖它的稀释闸里最小的那个,再按公式夹到 [loi,hii] 里。区间修改次数很多,用扫描线把区间拆成端点事件,从左扫到右维护当前生效的上界、下界。
- 稀释闸 [L,R] 上界 c:在位置 L 加入 c,在 R+1 删除 c。扫到 i 时,当前集合的最小值就是 hii;集合为空则没有上界。
- 回灌泵 [L,R] 下界 d:同样在 L 加入、R+1 删除。当前集合的最大值就是 loi;集合为空则 loi=0。
- 然后 ei=min(max(vi,loi),hii)。下界比上界更大时,结果会被上界卡住,这是公式本身的效果。
- 用可重集合(或带删除标记的堆)维护当前值,保证能正确处理重复的上界或下界。