Задача на Аналитика

Вам приходит два вида запроса.
1) Добавить число x в набор чисел.
2) Удалить число x из набора (если число x встречается несколько раз, то удалить их всех)

Ваша задача после каждого запроса найти дисперсию.
В рамках этой задачи дисперсию будет считать SUM(xi - x`)^2 / n
То есть сумма средне квадратичных отклонений от мат ожидания.

Решение:

Если честно могли бы лучше написать условия задач)

В общем для решение задачи нам понадобиться во первых словарь.
Пусть cnt = {} словарь, который хранит количество вхождения каждого числа.

Когда вам приходит первый тип запроса то вы увеличиваете количество вхождения, то есть cnt[x] += 1.

Когда второй тип мы просто удаляем этот ключ, то есть del cnt[x].

Давайте лучше посмотрим на сумму (xi - x`)^2 Если мы раскроем скобку, то получим
x1^2 + x2^2 + .... + xn^2 + n * x`^2 - 2 * (x1 + x2 + ... + xn) * x`.

И так чтобы считать дисперсию нам необходимо знать размер набора чисел, суммы чисел, суммы квадратов чисел x` мы можем всегда найти: x` = (x1 + .... + xn) / n

Создадим переменные
sum_sq, sum, n.

Когда приходит первый тип запроса:
sum_sq += x^2
sum += x
n += 1
cnt[x] += 1

Когда приходит второй тип запроса:
sum_sq -= x^2 * cnt[x]
sum -= x * cnt[x]
n -= cnt[x]
del cnt[x]

И так чтобы посчитать дисперсию у нас есть вся необходимая информация.
Дисперсия = (sum_sq + n * x`^2 - 2 * sum * x`) / n
Где x` = sum / n.

И так мы научились обрабатывать запросы за O(1)