新都市建設

各建物の高さは独立に決められます。したがって、各建物 $i$ について $\max(B_1,\ldots,B_{A_i})$ を求め、すべて足せば答えになります。

$h=2,3,\ldots,M$ の順に $B_h \gets \max(B_h,B_{h-1})$ と更新します。すると、 には元の数列の先頭 個の最大値が保存されます。答えは です。

時間計算量は $O(N+M)$、空間計算量は $O(N+M)$ です。