Автор, розробник, автор розбору: Андрій Столітній
Розглянемо випадок, коли ми маємо зібрати всі апельсини в координаті .
Для кожного апельсину ми маємо прийти до нього і прийти назад. Йти не в напрямку з апельсином не є оптимальним. Тоді ми маємо для кожного апельсину повторити маршрут k \rightarrow x_i \rightarrow k.
Відповідь виглядає як 2 \sum_{i=1}^{n} |x_i - k|, що можна розбити на
Тоді нам треба підтримувати такі прості суми. Можемо йти від найменшого до найбільшого, тоді підтримка таких сум буде очевидно.
Загальна складність: .