ARC120 A Max Add
$ a = (A_1, A_2, ..., A_k)について$ f(a)の値を$ O(\log N)で求められればよい. ここで, 次の性質を利用する.
$ \textbf{i = 2, 3, 4, ...}について, 現在のaの要素の最大値は必ず$ \textbf a_{i - 1}となる
この性質を用いると, $ aについての答えは, $ aの要素の最大値を$ Mとおくと, $ Mk + \sum_{i = 1}^k A_i + \sum_{i = 1}^{k - 1} \sum_{j = 1}^{i} A_jと表される.
3番目の項については, あらかじめ累積和をとり, 累積和の累積和を前計算しておくことにより高速に求められる. 2番目の項について, 実装例では$ aの要素の最大値を求めるパートにRMQを用いているので計算量が$ O(N \log N)となっているが, 累積Maxを前計算しておくことでも解くことができる. この場合計算量は$ O(N)となる.