丁寧に条件を考察したり実験して観察をしたりすることで、\(A _ n\) がはじめて正になるような操作の直前には \(\displaystyle A _ i=\max _ {i\lt j\leq n}H _ j\ (0\leq i\lt n)\) が成り立っていることがわかります。

はじめ \(\displaystyle\sum _ {i=0} ^ NA _ i=0\) であり、操作を一度行うごとに \(\displaystyle\sum _ {i=0} ^ NA _ i\) の値は \(1\) ずつ増加するので、\[\sum _ {i=0} ^ NA _ i=1+\sum _ {i=0} ^ {n-1}\max _ {i\lt j\leq n}H _ j\] の値が \(i=n\) に対する答えになります。

\(n\) が増えるとき \(\displaystyle X _ i\coloneqq\max _ {i\lt j\leq n}H _ j\) がどのように変化するかを考えることで、次のような問題に言い換えることができます。

長さ \(N\) の数列 \(X=(X _ 1,X _ 2,\dotsc,X _ N)\) がある。はじめ、\(X _ 1=X _ 2=\dotsb=X _ N=0\) である。 \(i=1,2,\ldots,N\) に対して順に次の操作を行う。

• \(1\leq j\leq i\) に対し、\(X _ j\leftarrow\max\lbrace X _ j,H _ i\rbrace\) と更新する。

それぞれの操作の直後の \(\displaystyle1+\sum _ {i=1} ^ NX _ i\) を求めよ。

この問題を解く方針はいくつかあります。

• stack を用いて \(\bigl(H _ i,(X _ j=H _ i\) となる \(j\) の個数\()\bigr)\) となる列を管理する
  • \(X _ j\leftarrow\max\lbrace X _ j,H _ i\rbrace\) では、stack の先頭の組 \((v,c)\) に対して \(v\leq H _ i\) である限り先頭を取り出すことを繰り返し、\(\bigl(H _ i,(\)取り出した \(c\) の合計\({}+1)\bigr)\) を追加する
  • \(\sum X _ i\) も stack の操作と同時に更新
• 遅延セグメント木を用いて区間更新・区間和クエリにする
  • \(X\) が単調減少列になるので、更新すべき区間は二分探索で求めることができる
• segment tree beats を用いて区間 chmax ・区間和クエリを処理する

\(1\) つめの方針では時間・空間計算量が \(\Theta(N)\) 、\(2\) つめと \(3\) つめの方針では \(\Theta(N\log N)\) 時間と \(\Theta(N)\) 空間になります。

実装例は以下のようになります。 この実装例では \(1\) つめの方針で解いています。

#include <iostream>
#include <utility>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    // 高さについて単調減少になるように (高さ, 個数) を管理する
    vector<pair<unsigned, unsigned>> rectangles;

    // 1 + ∑ 高さ × 個数
    unsigned long ans = 1;

    for (unsigned i = 0, H; i < N; ++i) {
        cin >> H;
        // 高さは H 、はじめ個数は 1
        unsigned count = 1;

        // H より低いものがある限り更新
        while (!empty(rectangles) && rectangles.back().first <= H) {
            const auto &[h, c] = rectangles.back();
            // 合計から h × c を引いて
            ans -= static_cast<unsigned long>(h) * c;
            // 個数を増やして
            count += c;
            // 列から取り除く
            rectangles.pop_back();
        }

        // 合計に H × count を足す
        ans += static_cast<unsigned long>(H) * count;
        rectangles.emplace_back(H, count);
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}