\[\mathrm{ans}(L, R) = \sum_{L \le l \le r \le R} \left(\left(\sum_{l \le i \le r} A_i\right) \bmod{M}\right)\]

とすると，求めたい答えは \(\mathrm{ans}(1, N)\) です． これを分割統治で求めます．

\(L = R = i\) のときは \(\mathrm{ans}(i, i) = A_i \bmod{M}\) です．

\(L < R\) のときは，\(m = \left\lfloor\frac{L + R}{2}\right\rfloor\) として，

\[\mathrm{ans}(L, R) = \mathrm{ans}(L, m) + \mathrm{ans}(m + 1, R) + \sum_{L \le l \le m < r \le R} \left(\left(\sum_{l \le i \le r} A_i\right) \bmod{M}\right)\]

を計算すればよいです． 前 \(2\) 項は再帰すればよいので，最後の項が（高速に）計算できれば十分です．

最後の項の対象となる区間 \([l, r]\) は，\(m\) を基準にして \([l, m]\) と \([m + 1, r]\) に分けられます． したがって，\(2\) つの累積和

\[ a_l = \left(\sum_{l \le i \le m} A_i \right) \bmod{M}, \quad b_r = \left(\sum_{m < i \le r} A_i \right) \bmod{M} \]

を用いて，

\[ \left(\left(\sum_{l \le i \le r} A_i\right) \bmod{M}\right) = \begin{cases} a_l + b_r & (a_l + b_r < M)\\ a_l + b_r - M & (a_l + b_r \ge M) \end{cases}\]

と書くことができます． これを \(L \le l \le m < r \le R\) に渡って足し合わせるので，各要素が足される回数を考えると，求めたいものは

\[(R - m) \cdot \sum_{L \le l \le m} a_l + (m - L + 1) \cdot \sum_{m < r \le R} b_r - \#\{\, (l, r) \mid L \le l \le m < r \le R,~a_l + b_r \ge M \,\} \cdot M\]

となります．（ \(\#\{\cdots\}\) は集合 \(\{\cdots\}\) の要素数を表す．） 前 \(2\) 項は素朴に \(\mathrm{O}(R - L)\) 時間で計算でき，また最後の項は \(a_l, b_r\) をそれぞれソートすれば尺取り法で \(\mathrm{O}(R - L)\) 時間で計算できます．

再帰するたびに区間の長さは半分程度になるので，再帰の深さは \(\mathrm{O}(\log N)\) です． また，各深さでのボトルネックは累積和をソートする部分なので，全体の計算量は \(\mathrm{O}(N (\log N)^2)\) です．

実装例 (C, 191 ms)