Разбор задачи про среднюю длину заказа 🤖

Здесь легко зацепиться за слово «средняя» и начать искать ответ заново после каждого запроса. Но к решению ведут три наблюдения.

1️⃣ Если пара пунктов выбирается равновероятно, искомое матожидание — это сумма расстояний между всеми парами, делённая на число пар.

2️⃣ Добавление или удаление пункта меняет только пары с его участием. Значит, достаточно пересчитать вклад одного пункта, а не всех остальных пар.

3️⃣ Чтобы найти этот вклад, не нужно обходить все пункты. Для пунктов слева и справа достаточно знать их количество и сумму координат. Эти данные быстро даёт дерево поиска или же дерево отрезков после сжатия координат.

Так задача о множестве расстояний сводится к поддержке двух простых величин: количества пунктов и суммы их координат. Добавление и удаление работают за O(log N) в случае дерева поиска.

А с какой идеи началось ваше решение? Делитесь в комментариях ⬇️

Ваш ШАД 🎓

#задачишад