首先考虑优惠券。

可以证明，如果使用两张及以上优惠券，那么除了最后实际生效的那一张之外，其余优惠券全部删除后，最终所在楼层不会发生变化。因此，最优策略中要么一张优惠券都不使用，要么至多使用一张。

同样地，在优惠券效果触发之前设置检查点也是没有必要考虑的，理由相同。

于是，对于每一张优惠券，只需考虑选择一个合适的 $t\in[L_i,R_i]$，从第 $t$ 关开始，以第 $X_i$ 层作为初始楼层，并在之后最多使用 $\left\lfloor\frac{W-Y_i}{D}\right\rfloor$ 次检查点，求最终能够到达的最大楼层。

定义 $f(i,j)$ 表示：在第 $i$ 个关卡之后，从第 $0$ 层开始，并最多使用 $j$ 次检查点时，最终能够到达的最大楼层。那么，对于每张优惠券，其答案为

$\max_{t\in[L_i,R_i]} f\!\left(t,\left\lfloor\frac{W-Y_i}{D}\right\rfloor\right)+X_i.$

于是，问题归结为如何高效维护 $f(i,j)$。

经过简单推导，可以得到如下转移方程：

$ f(i,j) = \min \! \left(f(i+1,j)+A_i,\;\min_{i < t}f(t,j-1)\right).$

虽然直接优化这一转移较为困难，但可以将所有 $f(i,j)$ 看成平面上的点进行观察。此时可以发现，$f(i,j+1)-f(i,j)\ (1\le i\le N)$ 的取值几乎不会发生变化。

更准确地说，满足

$f(i,j+1)-f(i,j)\neq f(i-1,j+1)-f(i-1,j)$

的二元组 $(i,j)$ 总数至多为 $N$ 个。证明略。

基于这一性质，可以设计如下算法。

初始时构造一个长度为 $N$ 的序列，其中

$S_N=0,\qquad S_i=S_{i+1}+A_{i+1}.$

该序列分别对应于 $f(0,0),f(1,0),f(2,0),\ldots$。

设

$d_i=f(i,1)-f(i,0).$

找到所有满足 $d_i\neq d_{i+1}$ 的位置，对序列的前缀不断执行“加上一个适当常数”的操作，即可使整个序列依次变为

$f(0,1),f(1,1),f(2,1),\ldots$

重复这一过程，就能够得到所有检查点数量对应的序列。这样，每张优惠券只需进行一次区间最大值查询即可得到答案。

为了找到 $d_i$ 发生变化的位置，只需找出所有满足

$S_i<\max(S_{i+1},S_{i+2},S_{i+3},\ldots,S_N)$

的下标 $i$。这一过程同样可以利用线段树完成。

若使用线段树结合二分搜索，时间复杂度为

$O(N\log^2N+Q\log N)$，

若在线段树上进行 tree walk，则可以进一步优化至

$O((N+Q)\log N)$。

(translated from korean by gpt 5.6)