[DS记录]Loj#3523. 「IOI2021」分糖果

**题意** ： 有 $n$ 个糖果盒，容量分别为 $A_{1\sim n}$ ，糖果数 $B_{1\sim n}$ 初始时为 $0$。 支持给出 $l,r,x$ ，对 $k\in[l,r]$ 将 $B_k$ 变为 $\max(\min(B_k+x,A_k),0)$。 给出 $m$ 次修改，求问最终 $B$ 的值。 $n,m\leq 2\times 10^5$。 ------------ - **扫描线** 将时间维和空间维转换。从左到右逐步考虑位置 $1\sim n$ ，维护当前的操作序列。 对于 $[l,r]$ 的修改，可以看做在 $l$ 处插入一个修改，在 $r+1$ 处删除一个修改。 ------------ - **把下界给扬喽** 观察两个操作叠加后的效果。 将操作写作映射（函数），对于不同的 $A$ ，这些映射也要改变。 初始映射为图 ①②（加减），这些映射复合后形如图 ③。  图 ③ 的复合规则相当复杂……看起来没什么救。这是同时有上下界的限制所导致的。 每个位置的上界各不相同，难以去除，考虑将下界的影响去除。 ------------ 记 $k$ 为 $B_i$ 最后一次变为 $0$ 的时间，则等效于从 $0$ 开始执行 $t_{k\sim m}$ 且无需考虑下界。 对于一组操作，若不考虑下界，答案只会变小，不会变大。 记 $f(A,t_{1\sim m})$ 为执行操作 $t_{1\sim m}$ 后 $B$ 的取值，$g(A,t_{1\sim m})$ 为执行操作 $t_{1\sim m}$ （但不考虑下界）后 $B$ 的取值。 结论 ： $f(A,t_{1\sim m})=\max_k g(A,t_{k\sim m})$ 。 现在我们不需要考虑下界了，观察简化后的映射的复合，为 $g$ 找一种简单的描述方式。  作减法时只是向下平移，作加法时就可能抵到上界，折点会向前移。 考虑最后一次抵住上界的 $k_*={\rm arg}\max_{k}\sum t_{1\sim k}$ ，此时纵坐标为 $A$ ，则最终的纵坐标为 $A+\sum t_{k_*+1\sim m}$。 当然，也有可能从头到尾都没抵到上界，此时最终的纵坐标为 $\sum t_{1\sim m}$。 综上，可以写出 ： $$g(A,t_{1\sim m})=\min\Big(A+\min_{k}\sum t_{k\sim m},\sum t_{1\sim m}\Big)$$ $$f(A,t_{1\sim m})=\max_j\Big\{\min\Big(A+\min_{j\leq k\leq n+1}\sum t_{k\sim m},\sum t_{j\sim m}\Big)\Big\}$$ 我们需要支持对 $t_{1\sim m}$ 进行单点修改，给出 $A$ 查询 $f(A,t_{1\sim m})$。 考虑二分答案，每次判定答案是否 $\geq C$。 注意到 $A+\min_{j\leq k\leq n+1}\sum t_{k\sim m}$ 随着 $j$ 的增大而增大，则满足条件的 $j$ 为一个后缀。 再查后缀 $\sum t_{j\sim m }$ 的最小值即可。 用线段树上二分可以改进为 $1\log$。 ```cpp ```