Портальная пушка

Переберем индекс i массива A, тем самым зафиксировав ai. Для фиксированного i нам нужно посчитать . Теперь раскроем |ai - bj|, рассмотрев два случая:

Выражения в обоих случаях одинаковы с точностью до знака, поэтому мы рассмотрим подсчет только первого из них. . Отсортируем массив пар (bi, i) по возрастанию и двоичным поиском найдем минимальный индекс minj, такой, что ai ≥ bminj.

Заметим, что чтобы посчитать сумму , достаточно посчитать префиксные суммы prefi = b1 + b2 + ... + bi на отсортированном массиве. Чтобы посчитать суммы и , также достаточно посчитать другие префиксные суммы на отсортированном массиве. Таким образом, мы научились для фиксированного i за вычислять сумму . Суммарное время работы — .