Переберем индекс i массива A, тем самым зафиксировав ai. Для фиксированного i нам нужно посчитать . Теперь раскроем |ai - bj|, рассмотрев два случая:
Выражения в обоих случаях одинаковы с точностью до знака, поэтому мы рассмотрим подсчет только первого из них. . Отсортируем массив пар (bi, i) по возрастанию и двоичным поиском найдем минимальный индекс minj, такой, что ai ≥ bminj.
Заметим, что чтобы посчитать сумму , достаточно посчитать префиксные суммы prefi = b1 + b2 + ... + bi на отсортированном массиве. Чтобы посчитать суммы
и
, также достаточно посчитать другие префиксные суммы на отсортированном массиве. Таким образом, мы научились для фиксированного i за
вычислять сумму
. Суммарное время работы —
.