求めたい値は

\[\displaystyle \sum_{l=1}^{N} \sum_{r=l}^{N} \left | \sum_{k=l}^{r} A_k \right |\]

で、この値は

\[\displaystyle \sum_{l=1}^{N} \sum_{r=l}^{N} \left | \sum_{k=1}^{r} A_k - \sum_{k=1}^{l-1} A_k \right |\]

に等しいため、 \(\displaystyle B_i := \sum_{k=1}^{i} A_k\) (\(B\) は 0-indexed で \(N+1\) 要素)とおくと答えは

\[\displaystyle \sum_{i=0}^{N} \sum_{j=i+1}^{N} | B_i - B_j |\]

と書けます。この値は、 \(B\) をソートした配列 \(B'\) を用いて

\[\begin {aligned}\displaystyle &\sum_{i=0}^{N} \sum_{j=i+1}^{N} ({B'}_j - {B'}_i) \\ = &\sum_{i=0}^{N} \sum_{j=i+1}^{N} {B'}_j - \sum_{i=0}^{N} \sum_{j=i+1}^{N} {B'}_i \\ = &\sum_{i=0}^{N} (i \times {B'}_i) - \sum_{i=0}^{N} ((N - i) \times {B'}_i) \\ = &\sum_{i=0}^{N} ((2i - N) \times {B'}_i) \end {aligned}\]

と書けるので、これを求めればよいです。

以上より、 \(O(N \log N)\) の時間計算量でこの問題を解くことができます。

計算途中のオーバーフローに注意してください。

実装例 (C++)