| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.
Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.
Для оценки рутинности работы сотрудника будем использовать следующую характеристику.
Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней.
Для каждого такого отрезка найдём количество различных типов заданий,
которые работник выполнял на протяжении этих дней, и просуммируем эти значения.
Полученную величину обозначим как Sd и будем называть её d-разнообразием.
Чем d-разнообразие выше, тем больше различных типов заданий выполнял
сотрудник. Профилем вариативности сотрудника будем называть массив
значений [S1, S2, …, Sn].
Требуется написать программу, которая по заданной последовательности a1, a2, …, an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.
В первой строке находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 ⋅ 105).
Во второй строке находится n целых чисел a1, a2, …, an — типы заданий, которое выполнял сотрудник (1 ≤ ai ≤ 109).
Выведите n целых чисел: S1, S2, …, Sn.
1 ≤ ai ≤ 109
1 ≤ n ≤ 2 ⋅ 105
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 12 | 1 ≤ n ≤ 50, 1 ≤ ai ≤ 50 | первая ошибка | |
| 2 | 10 | 1 ≤ n ≤ 50, 1 ≤ ai ≤ 109 | 1 | первая ошибка |
| 3 | 10 | 1 ≤ n ≤ 500, 1 ≤ ai ≤ 109 | 1,2 | первая ошибка |
| 4 | 12 | 1 ≤ n ≤ 5000, 1 ≤ ai ≤ 5000 | 1 | первая ошибка |
| 5 | 10 | 1 ≤ n ≤ 5000, 1 ≤ ai ≤ 109 | 1 - 4 | первая ошибка |
| 6 | 16 | 1 ≤ n ≤ 2 ⋅ 105, 1 ≤ ai ≤ 50 | 1 | первая ошибка |
| 7 | 30 | 1 ≤ n ≤ 2 ⋅ 105, 1 ≤ ai ≤ 109 | 1 - 6 | первая ошибка |
Рассмотрим, как вычисляются значения Sd в первом примере.
1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.
| Отрезок дней | Типы заданий | Количество различных |
|---|---|---|
| 1 - 1 | 1 | 1 |
| 2 - 2 | 3 | 1 |
| 3 - 3 | 2 | 1 |
| 4 - 4 | 1 | 1 |
| 5 - 5 | 2 | 1 |
Значение 1-разнообразия равно S1 = 1 + 1 + 1 + 1 + 1 = 5.
2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.
| Отрезок дней | Типы заданий | Количество различных |
|---|---|---|
| 1 - 2 | 1, 3 | 2 |
| 2 - 3 | 3, 2 | 2 |
| 3 - 4 | 2, 1 | 2 |
| 4 - 4 | 1, 2 | 2 |
Значение 2-разнообразия равно S2 = 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-разнообразия равно S3 = 3 + 3 + 2 = 8.
4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.
| Отрезок дней | Типы заданий | Количество различных |
|---|---|---|
| 1 - 4 | 1, 3, 2, 1 | 3 |
| 2 - 5 | 3, 2, 1, 2 | 3 |
Значение 4-разнообразия равно S4 = 3 + 3 = 6.
5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.
| Отрезок дней | Типы заданий | Количество различных |
|---|---|---|
| 1 - 5 | 1, 3, 2, 1, 2 | 3 |
Значение 5-разнообразия равно S5 = 3.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
В подзадаче 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(n2), которое проходит подзадачи 3--5. Заметим, что для решения подзадачи 4 этим методом не требуется перебор значений, которые встречаются в массиве, можно перебирать значения от 1 до 5000.
Для получения полного решения этим методом нужно избавиться от суммирования по c для каждого d. Для этого запишем все значения расстояний между соседними вхождениями c в один массив a для всех c. Тогда ∑c((n − L + 1) − D(d,c)) = ∑imax(a[i] − d + 1,0).
Чтобы посчитать эту сумму можно найти префиксные суммы массива ai и двоичным поиском находить позицию, где max(a[i] − d + 1,0) начинает равняться 0 для данного d. Альтернативно можно заметить, что эта позиция только растёт при росте d.