[JOI 2021 Final] 地牢 3 / Dungeon 3 题解

[JOI 2021 Final] 地牢 3 / Dungeon 3
题意

现在的题目情境不方便表述，我们换一种等价的题目情境：
一条公路上有 \(n+1\) 个加油站，第 \(i (1\le i \le n)\) 个加油站和第 \(i+1\) 个加油站之间的距离为 \(a_i\)，且第 $i (1\le i \le n) $ 个加油站的油价为 \(b_i\) 每升，一升油可以让汽车行驶一单位距离。\(m\) 次询问，每次询问给出旅程的起点 \(S\)，终点 \(T\)，以及汽车的邮箱容量 \(U\)，问在初始邮箱为空，且中途任何时刻邮箱储存的油都不能超过 \(U\) 的前提下，从 \(S\) 开到 \(T\) 所需要的最少花费是多少。
题解

把公路看成数轴，\(1\) 号加油站为原点，记 \(s_i=\sum_{jU\) 显然无解。为了避免讨论无解的情况，在下面的讨论中，我们认为：出现这种情况时，你只需要花费 \(U\) 的代价就可以直接跳到 \(i+1\)，或者说直接令 \(a_i\gets \min(a_i,U)\)，显然这不会让除了 \((i,i+1)\) 之外的任何两个加油站从原先 \(>U\) 的距离变成 \(\le U\) 的距离。
从大到小对 \(S\) 扫描线，同时维护加油站的关于价格单调递减的单调栈，假设现在扫到 \(i\)，我们已经知道了 \(i+1\) 的答案以及 \(id\) 数组（当然我们并不需要显示的维护这个数组）。在用 \(i\) 更新完单调栈之后，现在的栈顶 \(j\) 就是下一个价格比 \(i\) 小的加油站，那么根据上面的贪心我们需要把点 \(s_i\) 之后的 \(\min(U,s_j-s_i)\) 个格子的 \(id\) 全都覆盖成 \(i\)，同时修改对应的代价，最后再加上开头新增的 \(a_i\) 个格子的代价。
具体的，在更新单调栈的过程中，假设当前栈顶是 \(x\)（他即将被弹掉），下一个栈顶是 \(y\)，我们已经成功更新了 \(s_x\) 及以前的格子的代价，现在要更新 \([s_x,s_y]\) 中的格子：
<ul> \(U\le s_x-s_i\)（即使中间某些 \(a_k\) 变成了 \(\min(a_k,U)\)，仍然改变不了 \(U\le s_x-s_i\) 的事实）：\(i\) 最多让 \(R\) 扩展到 \(s_x\)，不会影响后面的格子，不需要更新。
\(U> s_x-s_i\)（此时 \(a[i,x-1]\) 一定都 \(

东西不错很实用谢谢分享

yyds。多谢分享