本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-09 09:56:17

:::::info[闲话]{open} 困难题，怎么有人写题解了。 ::::: :::::info[题目基本信息] 考察：倍增，贪心（省选/NOI-）。
题目简介：
有 $n$ 个城市，相邻两个城市间的距离构成了数列 $\{l_{n-1}\}$，一个人他的油箱最多能装 $m$ 个单位的油，他进行了 $q$ 次行程，对于第 $i$ 次行程，初始时油箱里有 $v_i$ 个单位的油，他要从城市 $s_i$ 跑到城市 $t_i$，每走一个单位长度的距离会消耗一个单位的油，每当他处于一个城市 $j$，它能付出 $a_j$ 的代价购买一个单位的油，询问他想要抵达 $t_i$ 最少需要多少个单位的油。
数据范围：

• $1\le n,q\le 10^6$
• $1\le m\le 10^{18}$
• $\forall i\in[1,n),1\le l_i\le\min(V,10^6)$
• $\forall i\in[1,n],1\le a_i\le 5\times 10^6$
• $\forall i\in[1,m],1\le s_i<t_i\le n$
• $\forall i\in[1,m],0\le v_i\le V$ ::::: 这个题我们先考虑贪心刻画他行程的过程，当他处于一个城市 $s$ 时，找到如果在他这里装满油能跑到的最远的城市，如果在这一段中没有比它的 $p_s$ 更小的城市 $d$（下文简称情况 1），那么我们会令 $d$ 为这段中 $p_d$ 最小的城市中最远的城市（最远是因为这个城市的 $p_s$ 已经很优，我们得让他多跑），否则（下文简称情况 2）我们找到最近的比 $p_s$ 更小的 $d$，跑到 $d$，重复该过程直到跑到终点。
  我们发现可以使用倍增来优化这个过程（存在线段树做法，但是我太菜了不会），具体地，对于前面的预处理，我们设 $\{pos_n\}$ 表示这些城市与城市 $1$ 的距离（同时这也表示这些城市的位置），可以对 $\{l_{n-1}\}$ 求前缀和得到，再设 $r_i$ 在情况 1 表示城市 $i$ 最远能到达的城市，在情况 2 表示城市 $i$ 的后继 $d$，这个容易维护，最远能到达的城市可以双指针求出，后继 $d$ 可以单调栈求出，两者取一个 $\min$ 就是 $\{r_n\}$。
  维护完 $\{r_n\}$ 后设 $nxt_{i,j}$ 表示城市 $i$ 进行 $2^j$ 次跑后会到达哪个城市，根据上述容易求出 $nxt_{i,0}$（区间查询 $p_i$ 最小的城市中最远的城市可以使用 ST 表），倍增容易求得所有的 $nxt_{i,j}$。
  再设 $p_{i,j}$ 表示从城市 $i$ 开始进行 $2^j$ 次跑后加的油能跑到的位置，对于情况 1，我们令 $p_{i,0}\leftarrow pos_i+m$，对于情况 2，我们令 $p_{i,0}\leftarrow pos_{r_i}$，倍增也容易求得所有的 $p_{i,j}$。
  最后我们要算答案，所以我们还需要设 $f_{i,j}$ 表示从城市 $i$ 开始进行 $2^j$ 次跑后所需的油量，初始时我们令 $f_{i,0}\leftarrow (p_{i,0}-pos_i)\cdot a_i$，但是倍增时我们不能直接令 $f_{i,j}\leftarrow f_{i,j-1}+f_{nxt_{i,j-1},j-1}$，这样在 $i$ 跑 $2^{j-1}$ 次触发情况 1 时会有一段距离算重了，这时正确的倍增转移为： $$f_{i,j}\leftarrow f_{i,j-1}+f_{nxt_{i,j-1},j-1}-(p_{i,j-1}-pos_{nxt_{i,j-1}})\cdot a_{nxt_{i,j-1}}$$ 这样我们就做完了所有的预处理，现在我们来回答询问。
  先特判掉 $pos_{t_i}\le pos_{s_i}+v_i$。
  现在我们考虑消去 $v_i$ 的影响，这个非常妙妙妙，注意到这个答案就是在 $v_i=0$ 时 $pos_{s_i}$ 到 $pos_{t_i}$ 的答案减去在 $v_i=0$ 时 $pos_{s_i}$ 到 $pos_{s_i}+v_i$ 的答案，这样就消去了 $v_i$ 的影响。
  在倍增求 $v_i=0$ 时的答案时，我们不断跳逼近（但不到达，因为到达后可能后面会跟随一小段距离导致算多，没算的这一部分最后算上就好啦），与倍增过程所维护的信息类似，就不过多赘述。
  最终时间复杂度为 $\Theta((n+m)\log n)$，空间复杂度为 $\Theta(n\log n)$。

code
同机房大佬 KSCD_ 实现的线段树做法也在其中（模拟赛赛时代码）。