操作対象の区間として \(B_1,\ldots,B_N\) が消費魔力となる極大なもののみを考え、対応する二分木(Cartesian treeと呼ばれます)を考えるところまでは公式解説と同じです。

\(i=1,2,\ldots,h_{max}\) の順に次のように操作をすることを考えます。

• \(h_ j\geq i\) であるようなモンスターの体力をちょうど \(1\) ずつ減らせるような区間の選び方のうち消費魔力が最小になるものを選び、操作をする。

この時、消費した魔力の総和が答えです。

証明
最適解において選ばれる区間の多重集合を \(I\) とします。この時、\(i=1,2,\ldots,h_{max}\) の順に \(I\) から \(h_j \geq i\) であるようなモンスターの体力をちょうど \(1\) ずつ減らせるように区間を選び、削除することが可能です。特に、重複部分を持つ区間が必ず包含関係にあることに気を付けると、区間が重複した場合は大きくない方を削除することで区間の重複を解消できます。
このため、上述の \(1,2,\ldots,h_{max}\) 回目の操作方法は独立に考えることが出来、毎回消費魔力が最小となるように区間を選べば最適解が得られます。

二分木の各頂点 \(v\) に対し、\(x_v\) を対応する区間内のモンスターのうち \(i\geq h_j\) を満たすものの体力を \(1\) ずつ減らすのに使う魔力の量の最小値とします。\(i\) の増加に伴って考慮するモンスターが減るという変化が最大 \(N\) 回起きますが、各段階において根 \(r\) における \(x_r\) の値を高速に求められれば良いです。

\(v\) の状態を以下の \(3\) つに分類します。

1. \(h_v \geq i\) を満たす。この時、\(x_v = b_v\) である。
2. \(h_v \lt i\) かつ、\(b_v\) が \(v\) の子の \(x\) の値の総和より小さい。この時、\(x_v=b_v\) である。
3. \(h_v \lt i\) かつ、\(b_v\) が \(v\) の子の \(x\) の値の総和以上である。この時、\(x_v \) は \(v\) の子の \(x\) の値の総和である。

考慮すべきモンスターが減った時、対応する頂点は状態 \(1\) から \(2\) になります。また、子の \(x\) の値の総和と自身の \(b\) の大小によっては \(x\) の値が更新され、状態が \(2\) から \(3\) になります。そのうえ、\(x\) の値が更新された場合はその親について、状態 \(3\) ならば値が更新され、状態 \(2\) の場合も状態 \(3\) になるかどうかを確認して適切に処理する必要があります。

しかし、よく考えるとある頂点 \(v\) において \(x_v\) が更新された場合の処理は次のもので十分です。

• \(v\) から始めて、現在の頂点の親が状態 \(3\) ならば親へ行く、ということを繰り返した場合に繰り返しが終了する頂点を \(u\) とする。\(x_u\) を更新する。そして、\(u\) の親の状態が変化するか・\(x\) の更新が発生するかを調べる。

頂点 \(u\) は、UnionFindの併合において経路圧縮のみを用いるもの、およびそれに類する実装を用いることで高速に求められます(頂点が状態 \(3\) になった場合に子との間に辺を張ることになります)。
計算量は \(B\) のソート等がボトルネックとなり、全体で \(\mathrm{O}(N\log N)\) です。