公式解説を前提とします。

\(L_i, R_i\) は適切な実装により全体で線形時間で求められるため、この問題は時間計算量 \(\Theta(N)\) で解くことができます。しかし、これを最悪 \(\Theta(N \log N)\) に悪化させることで、区間に等差数列を加算する処理を、区間に定数を加算する処理に置き換えることができます。細かい off-by-one のエラーなどを防ぐことが期待されます。

\(l=0,1,\ldots,L_i\) のそれぞれに対し、\(1+l \leq k \leq 1+l+R_i\) なる \(k\) について \(ans[k]\) に \(A_i\) を加算する、という解法を考えます。確かに正しい答えを得ることはできますが、\(L_i = i-1\) となるケースで区間加算が \(\Theta(N^2)\) 回行われるため、実行時間制限に間に合いません。

ここで、\(L_i > R_i\) となる \(i\) においては、\(r=0,1,\ldots,R_i\) のそれぞれに対し \([1+r, 1+r+L_i]\) に加算することにします。これで区間加算の回数は \(\sum_{i=1}^N (1+\min(L_i, R_i))\) となりますが、実はこれは \(O(N \log N)\) となることが知られています。Cartesian Tree 上で部分木のサイズでマージテクを行っているとみなせるためです。

以上より、区間加算を imos 法を用いて実装することで、\(O(N \log N)\) 時間でこの問題を解くことができます。なお、Cartesian Tree は線形時間で構築でき、これを用いることで \(L_i, R_i\) も線形時間で求めることができます。解説放送も参照してください。