Задача H ШАД 2025

На этот раз разберём задачу H из субботнего экзамена, второго этапа отбор в ШАД. За эту задачу каждый должен был забирать баллы для прохода в следующий этап. Такие задачи по большей части учебные, в очередном отборе в шад убеждаемся, что для успешного закрытия алгосов на экзамене достаточно лишь базовой практики по популярным темам, так что даже вам не нужно набираться реального олимпиадного опыта с задачами спортивного программирования, а для подготовки достаточно непродолжительного времени.

Условие задачи
На отрезке [0, L] (координата L ≤10^6) множество точек.
Всегда присутствуют концы 0 и L. Поддерживаются запросы:
1.добавить новую точку X;
2.удалить существующую точку X;
3.вывести среднее по всем расстояниям между двумя точками в множестве

Разбор
Для начала выведем формулу среднего, answer = Sum / Binom(n, 2) = Sum*2 / (n * (n - 1)) (Binom(n, 2) - это количество возможных пар расстояний, а Sum - сумма по всем расстояниям в паре). В таком случае наша задача сводится к быстрому поддержанию суммы Sum.
Рассмотрим как меняется значение Sum при изменении в точке X (например добавления, а случай удаления абсолютно так же считается, просто учитывается с противоположным знаком).
Все точки слева внесут вклад в сумму равный count(x[i] < X) * X - sum(x[i] | x[i] < X) (то есть мы просто сумму разниц разложим на разницу сумм (сумма элементов X и сумма всех элементов, которые левее, обозначим sum_left), правая сумма вычисляется по аналогичной логике.
delta_S = count(x[i] < X) * X - sum_left + sum_rigtht - count(x[i] > X) * X
Суммы (sum_left, sum_right) и количества (count) мы можем вычислять с помощью структур за O(log L) (например фенвик либо ДО и т п). Далее попробуем оптимизировать эту асимптотику, хотя log L и так достаточно для решения данных ограничений. Считаем все запросы, запомним, а координаты все когда либо использованных значений сожмем (воспользуемся идеями сжатися координат), это позволит нам асимптотику O(log q). Соответственно итоговая асимптотика будет O(qlog q).

@algoses