令 $f_i$ 代表考虑前 $i$ 个最少花多少钱，则能立刻买价值为 $v$ 的剑当且仅当 $x+pre_i-f_i\geq v$，其中 $pre$ 是 $r$ 的前缀和。记 $w(v)$ 是攻击力 $\geq v$ 的剑中的最小价值，则：

$$f_i=\min\limits_{i-k\leq j< i,x+pre_j-f_j\geq w(\max\limits_{j< k\leq i}h_j)}(f_j+w(\max\limits_{j< k\leq i}h_j))$$

说人话就是只需要关心当前新加的这一段中生命值最大的怪兽。容易想到在 $h$ 的笛卡尔树上分治转移。枚举右子树的所有点，线段树维护 dp 值已经确定的位置上的 $pre_j-f_j$，需要找出一段区间中 $pre_j-f_j\geq v$ 且 $f$ 最小的位置。由于 $f$ 不降，线段树二分找到第一个 $pre_j-f_j\geq v$ 的位置即可。

不过这样最坏复杂度还是 $O(n^2)$。考虑左子树大小更小的时候枚举左子树主动转移，这样根据启发式合并分析复杂度得到枚举量是 $O(n\log n)$。现在需要对一段区间的 dp 值 chkmin，同样线段树维护即可。总时间复杂度 $O(n\log^2 n)$。注意转移一个子树的时候要先把根转移好。