题目大意

有一个 $N+1$ 层的地牢，从第 $i$ 层到第 $i+1$ 层需要消耗能量 $A_i$。每层有治疗泉，在第 $i$ 层花费 $B_i$ 金币可以增加 $1$ 点能量（不能超过最大能量 $U_j$）。每个玩家从 $S_j$ 层出发到 $T_j$ 层，初始能量为 $0$，求最小金币花费或判断是否可行。

算法思路

核心观察

1. 可行性判断：如果从 $S_j$ 到 $T_j-1$ 中某段 $A_i > U_j$，则不可行。
2. 贪心策略：在需要补充能量时，应该选择之前经过的层中 $B_i$ 最小的治疗泉。
3. 离线处理：将所有查询按照起点分组处理。

关键技巧

1. 预处理

• ST表：预处理 $A_i$ 的区间最大值和 $B_i$ 的区间最小值，用于快速查询
• 前缀和：$X[i]$ 表示从第 $1$ 层到第 $i$ 层的能量消耗总和

2. 关键层确定

对于每个查询 $(S, T, U)$：

• 找到关键层 $m$：在区间 $[\max(S, \text{GetX}(X[T]-U)), T-1]$ 中 $B_i$ 最小的层
• 在关键层 $m$ 处补充能量到刚好能到达 $T$ 层

3. 树状数组优化

• 使用 BIT 维护不同能量需求下的费用
• 从后往前扫描，维护一个单调栈来找到"下一个更便宜的泉"

算法流程

1. 预处理：

   • 读入 $A_i, B_i$，计算前缀和 $X[i]$
   • 构建 ST 表用于区间最大值/最小值查询

2. 查询预处理：

   • 对于每个查询，先判断可行性
   • 找到关键层 $m$，计算基础花费
   • 将查询离线存储

3. 离线处理：

   • 从后往前扫描每一层
   • 维护单调栈保证 $B_i$ 递增
   • 用 BIT 维护费用信息
   • 处理以当前层为起点的查询

4. 输出答案

复杂度分析

• 时间复杂度：$O((N+Q)\log N)$
  • ST 表预处理 $O(N\log N)$
  • 单调栈 + BIT 操作 $O(N\log N)$
  • 查询处理 $O(Q\log N)$
• 空间复杂度：$O(N\log N + Q)$

关键实现细节

单调栈维护

std::stack<int> sta;
sta.push(n + 1);
for_(i, n, 1) {
    while (B[i] < B[sta.top()]) {
        // 弹出栈顶，更新BIT
    }
    // 当前层入栈，更新BIT
}

费用计算

• 基础费用：在关键层 $m$ 补充 $(X[T] - X[m])$ 点能量
• 额外费用：通过 BIT 计算其他层的补充费用

总结

本题是一个综合性的优化问题，主要技巧包括：

1. ST表快速区间查询
2. 离线处理优化多次查询
3. 单调栈维护下一个更便宜的治疗泉
4. 树状数组高效维护费用信息
5. 贪心策略选择最优治疗时机