Moving Points - #624 f - tac

#seg tree #BIT #pbds

問題
n 点と, その位置, 速度が与えられる.
すべての点の組み合わせで, その最小距離の合計を答える.
ある時刻の, 距離の合計の最小値を答えるのではないことに注意.

2 つの点が出会わないのであれば, 最初の距離の差
出会うなら, 0

ダブりがないよう, x に関して i を走査し, j < i となる j すべてを考える
組み合わせ (i, j) に関して j < i より一意

2 つの点が出会わない場合の最初の距離の差が答えなので, x に関して i より小さく, i より遅い j を j' とすると,
$\sum_{}^{} (x_i - x_j')$