A：

题目可变为：从一个点 $x$ 走到左侧或右侧第一个 $\geq y(y \leq x)$ 的位置需要花费 $l_{x}$ 或 $r_{x}$ 的代价，多次查询最短路。

首先观察一个点 $x$ 只往 $a$ 值高于自己的位置走能走到哪些点。

找到左侧从 $x$ 出发的后缀 $\max$ ，右侧从 $x$ 出发的前缀 $\max$ ，显然可以在这些位置之间左右横跳，并且由于 $l_{i}$ 单增， $r_{i}$ 单减的性质，如果想要走到这些点，一定不会在其中一步不往上走；同理如果想从这些点往 $x$ 走，也不会在其中一步不往下走。

先假设 $a$ 是一个排列，然后我们构造一棵 $\mathcal O(n)$ 个点的树，对于一个点 $x$ ，找到右侧第一个 $x^{\prime}$ 满足 $a_{x^{\prime}}>a_{x}$ （左侧同理），把这个 pair 看做一个点，将它的父亲设为 $x$ 往左（右）走一步与 $x^{\prime}$ 构成的 pair 对应的点。

这样，对于一个 $\left(x, x^{\prime}\right)$ 的点，如果已知到 $x$ 的最短路径长度与到 $x^{\prime}$ 的最短路径长度，其到它的父亲对应的最短路径长度即为乘上一个 $2 \times 2$ 的矩阵（ $(\max ,+)$ 乘法），倍增一下即能快速算出儿子到祖先的最短路（祖先到儿子同理）。

对于一名旅客，设起点为 $s$ ，终点为 $t$ ，不妨设 $s<t$ ，设中间 $a$ 的最大值为 $a_{p}$ 。最短路一定是 $s \rightarrow p \rightarrow t$ 或者 $s$ 走到 $s$ 左侧第一个 $>a_{p}$ 的点再走到 $t$ 右侧第一个 $>a_{p}$ 的点再走到 $t$ ，这两种情况中间过程均可表示为树上的祖先与儿子之间的最短路，直接倍增求值即可。

一道只需要倍增的数据结构题。

时间复杂度 $\mathcal O(n \log n)$ 。

B：

不太懂放这么个打表题想表达什么。

C：

初始矩阵：

$$E= \left[ \begin{matrix} 0&0&1 \end{matrix} \right]$$

加入一个 $t$：

$$T= \left[ \begin{matrix} 1&0&0\\ 0&0&-1\\ 0&1&2\\ \end{matrix} \right]$$

加入一个 $d$：

$$D= \left[ \begin{matrix} 0&0&-1\\ 0&1&0\\ 1&0&2\\ \end{matrix} \right]$$

设 $X=T\times D$，每次转移就是 $X\leftarrow X\times X\times T$。

预处理前 $10^6$ 个转移矩阵即可获得 51pts。

注意到

对于 $n>799039878$ 时答案为 $2^{n-799039878}$，剩下的分块打表即可。

不太懂是怎么注意到的。