Задача 3. Борьба с рутиной ≡

Условие

Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом a_i.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как S_d и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S₁, S₂, …, S_n].

Требуется написать программу, которая по заданной последовательности a₁, a₂, …, a_n типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

Формат входных данных

В первой строке находится единственное целое число n  — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 ⋅ 10⁵).

Во второй строке находится n целых чисел a₁, a₂, …, a_n  — типы заданий, которое выполнял сотрудник (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите n целых чисел: S₁, S₂, …, S_n.

Ограничения

1 ≤ a_i ≤ 10⁹

1 ≤ n ≤ 2 ⋅ 10⁵

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

Рассмотрим, как вычисляются значения S_d в первом примере.

1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.

Значение 1-разнообразия равно S₁ = 1 + 1 + 1 + 1 + 1 = 5.

2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.

Значение 2-разнообразия равно S₂ = 2 + 2 + 2 + 2 = 8.

3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.

Значение 3-разнообразия равно S₃ = 3 + 3 + 2 = 8.

4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.

Значение 4-разнообразия равно S₄ = 3 + 3 = 6.

5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.

Значение 5-разнообразия равно S₅ = 3.

Примеры тестов

5
1 3 2 1 2

5 8 8 6 3 

3
10 10 10

3 2 1 

Разбор

В подзадаче 1 для этого можно использовать массив элементов типа bool, отмечая встретившиеся значения, в подзадаче 2 встретившиеся значения можно сложить, например, в std::set, либо в массив, отсортировать и найти число различных значений. Наконец, отметим, что поскольку n ≤ 50, можно обойтись даже без сортировки, для каждого элемента проверяя, не встречался ли он раньше.

Решение с std::set при аккуратное реализации может также пройти подзадачу 3, альтернатива  — отсортировать значения на отрезке с помощью std::sort и посчитать количество различных значений.

Улучшим это решение.

Зафиксируем длину отрезка d и посмотрим для каждого числа c в массиве то, в скольких отрезках оно не встречается. Посмотрим на два соседних вхождения числа, если расстояние между ними x ≥ d, то существует ровно d − x + 1 отрезок, лежащий между ними. Просуммировав эту величину по всем парам соседних вхождений числа, а также между началом массива и первым числом и между последним числом и концом массива, получим количество отрезков, которые не включают в себя ни одно вхождение данного числа.

Обозначим эту величину за D(d, c). Тогда ответ для заданной длины отрезка  — это ∑((n − L + 1) − D(d,c)). Если посчитать эту сумму наивно, получим решение за O(n²), которое проходит подзадачи 3--5. Заметим, что для решения подзадачи 4 этим методом не требуется перебор значений, которые встречаются в массиве, можно перебирать значения от 1 до 5000.

Для получения полного решения этим методом нужно избавиться от суммирования по c для каждого d. Для этого запишем все значения расстояний между соседними вхождениями c в один массив a для всех c. Тогда ∑_c((n − L + 1) − D(d,c)) = ∑_imax(a[i] − d + 1,0).

Чтобы посчитать эту сумму можно найти префиксные суммы массива a_i и двоичным поиском находить позицию, где max(a[i] − d + 1,0) начинает равняться 0 для данного d. Альтернативно можно заметить, что эта позиция только растёт при росте d.