ABC351 F - Double sum - zero-two's blog

問題リンク
F - Double Sum

解法

問題の式を次のように変形する。

$\displaystyle{ \sum_{i=1}^N\sum_{j=i+1}^N\max(A_j-A_i, 0)=\sum_{i=1}^N\sum_{j=i+1}^N \{\max(A_j,A_i)-A_i\} }$

したがって、

各 $i$ に対し, $i < j$ かつ $A_i < A_j$ をみたす $j$ について, ( $A_j$ の総和) - ( $j$ の個数) $× A_i$

を求め、その総和を取ればよいことが分かる。

これは $i$ を $N$ から $1$ の順に考えると、

の2本のsegment tree(どちらも一点加算区間総和)を使えば良いので、計算量は $O(N\log N)$
座標圧縮が必要なので注意。