Задача №114527. Борьба с рутиной
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.
Рассмотрим работу сотрудника в течение \(n\) последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в \(i\)-й день, целым числом \(a_i\).
Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число \(d\) и рассмотрим все отрезки из \(d\) подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как \(S_d\) и будем называть её \(d\)-разнообразием. Чем \(d\)-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений \([S_1, S_2, \ldots, S_n]\).
Требуется написать программу, которая по заданной последовательности \(a_1, a_2, \ldots, a_n\) типов выполняемых сотрудником заданий вычисляет его профиль вариативности.
В первой строке находится единственное целое число \(n\) — количество последовательных рабочих дней, которые необходимо проанализировать (\(1 \leq n \leq 2 \cdot 10^5\)).
Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — типы заданий, которое выполнял сотрудник (\(1 \leq a_i \leq 10^9\)).
Выведите \(n\) целых чисел: \(S_1, S_2, \ldots, S_n\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 12 | \(1 \leq n \leq 50\), \(1 \leq a_i \leq 50\) | первая ошибка | |
| 2 | 10 | \(1 \leq n \leq 50\), \(1 \leq a_i \leq 10^9\) | 1 | первая ошибка |
| 3 | 10 | \(1 \leq n \leq 500\), \(1 \leq a_i \leq 10^9\) | 1, 2 | первая ошибка |
| 4 | 12 | \(1 \leq n \leq 5000\), \(1 \leq a_i \leq 5000\) | 1 | первая ошибка |
| 5 | 10 | \(1 \leq n \leq 5000\), \(1 \leq a_i \leq 10^9\) | 1 – 4 | первая ошибка |
| 6 | 16 | \(1 \leq n \leq 2 \cdot 10^5\), \(1 \leq a_i \leq 50\) | 1 | первая ошибка |
| 7 | 30 | \(1 \leq n \leq 2 \cdot 10^5\), \(1 \leq a_i \leq 10^9\) | 1 – 6 | первая ошибка |
Рассмотрим, как вычисляются значения \(S_d\) в первом примере.
1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.
| Отрезок дней | Типы заданий | Количество различных |
| 1 – 1 | \(1\) | 1 |
| 2 – 2 | \(3\) | 1 |
| 3 – 3 | \(2\) | 1 |
| 4 – 4 | \(1\) | 1 |
| 5 – 5 | \(2\) | 1 |
Значение \(1\)-разнообразия равно \(S_1 = 1 + 1 + 1 + 1 + 1 = 5\).
2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.
| Отрезок дней | Типы заданий | Количество различных |
| 1 – 2 | \(1, 3\) | 2 |
| 2 – 3 | \(3, 2\) | 2 |
| 3 – 4 | \(2, 1\) | 2 |
| 4 – 5 | \(1, 2\) | 2 |
Значение \(2\)-разнообразия равно \(S_2 = 2+2+2+2 = 8\).
3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.
| Отрезок дней | Типы заданий | Количество различных |
| 1 – 3 | \(1, 3, 2\) | 3 |
| 2 – 4 | \(3, 2, 1\) | 3 |
| 3 – 5 | \(2, 1, 2\) | 2 |
Значение \(3\)-разнообразия равно \(S_3 = 3+3+2 = 8\).
4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.
| Отрезок дней | Типы заданий | Количество различных |
| 1 – 4 | \(1, 3, 2, 1\) | 3 |
| 2 – 5 | \(3, 2, 1, 2\) | 3 |
Значение \(4\)-разнообразия равно \(S_4 = 3+3 = 6\).
5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.
| Отрезок дней | Типы заданий | Количество различных |
| 1 – 5 | \(1, 3, 2, 1, 2\) | 3 |
Значение \(5\)-разнообразия равно \(S_5 = 3\).
5 1 3 2 1 2
5 8 8 6 3
3 10 10 10
3 2 1