ABC186 D Sum of difference
Diff 436.
まずAを昇順にソートしておく. すると絶対値は外せて, さらに各iについて1個のΣの数式で表すことができるようになる. あとは式変形すると(A_iの右にある要素の和)-(その個数 × A_i)の形になってこれは各iについて和を差分更新することによってO(1)で解ける.
実装例:
https://atcoder.jp/contests/abc186/submissions/18869884