転倒数はマージソートしつつ数え上げる分割統治法で求めることができますが、その方法をこの問題に適用することを考えます。

以下ざっくりとした説明です。増加列\(L\)と増加列\(R\)をマージしつつ、\(\sum_{y \in L, x \in R} \max(y-x, 0)\)を求めることを考えます。尺取り法をしながら\(L\)と\(R\)をマージするわけですが、ここでは「\(R\)の要素を指すポインタ\(j\)を1増やすごとに、\(L\)の要素を指すポインタ\(i\)を\(L[i]<R[j]\)が成り立つぎりぎりまで増やす」ことを繰り返すような実装で考えます。

ここで、\(y=R[j]\)で固定して考えると、

\[\sum_{x \in L} \max(R[j]-x, 0) = \sum_{0 \leq t \leq i} R[j]-L[t] = (i+1) \times R[j] - \sum_{0 \leq t \leq i} L[t]\]

となります。\(L\)の\(i\)までの累積和を保持しつつ尺取り法を行えば、上記の和は\(O(1)\)で計算できます。

全体の計算量は\(O(N \log N)\)です。

pythonでの提出例 (350ms)