P11151 [THUWC 2018] 明天的太阳会照常升起 题解

zrl123456 · 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_ 实现的线段树做法也在其中（模拟赛赛时代码）。