Задача №114578. Башни 2.0
В компьютерной игре есть \(n\) башен, высота \(i\)-й башни равна \(a_i\) метров. Определим расстояние между двумя башнями с индексами \(i\) и \(j\) как \(|i - j|\). Разрешается прыгнуть с \(i\)-й башни на \(j\)-ю башню тогда и только тогда, когда не существует такого индекса \(1 \le k \le n\), такого, что расстояние от \(i\)-й до \(j\)-й башни не меньше расстояния от \(i\)-й башни до \(k\)-й башни, и \(k\)-я башня имеет большую высоту, чем \(j\)-я. Башня \(j\) достижима из башни \(i\) если существует последовательность корректных прыжков, которая начинается в \(i\)-й башне и заканчивается в \(j\)-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.
Первая строка входных данных содержит одно целое число \(n\) (\(1 \le n \le 500\,000\)) — количество башен.
Вторая строка входных данных содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_n \le 10^9\)) — высоты башен.
Выведите \(n\) чисел, \(i\)-е из которых должно быть равным количеству башен, достижимых из \(i\)-й башни.
В первом примере с \(1\)-й башни можно прыгнуть на башни \(1\) и \(5\). Любая другая башня имеет меньшую высоту, чем башня \(1\), поэтому туда нельзя прыгнуть (в качестве \(k\) можно выбрать \(1\)). Множество достижимых из \(1\)-й башни также состоит из башен \(1\) и \(5\). Со второй башни можно прыгнуть на башни \(1\), \(2\), и \(5\), они же являются множеством достижимых. С третьей башни можно прыгнуть на башни \(2\), \(3\), \(5\). Однако, башня \(1\) также является достижимой, поскольку можно сделать два прыжка: \(3 \to 2 \to 1\). Таким образом, получается \(4\) достижимые башни. С \(4\)-й башни можно прыгнуть на башни \(4\) и \(5\), они же являются единственными достижимыми. Из \(5\)-й башни достижима только она сама.
Во втором примере из \(1\)-й и из \(2\)-й башни достижимы башни \(1, 2, 3, 4, 5\). Из \(3\)-й башни достижимы башни \(3, 4, 5\). Из \(4\)-й и \(5\)-й башни достижимы башни \(4, 5\). Из \(6\)-й башни достижимы башни \(4, 5, 6\). Из \(7\)-й башни достижимы башни \(4, 5, 6, 7\).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обозначим за \(C\) высоту самой высокой башни.
| Группа | Балл | n | C | Дополнительно | Зависимости |
| 0 | 0 | Тесты из условия | |||
| 1 | 18 | \(n \le 100\) | \(C \le 10^9\) | 0 | |
| 2 | 11 | \(n \le 2000\) | \(C \le 10^9\) | Все \(a_i\) различны | |
| 3 | 9 | \(n \le 200\,000\) | \(C \le 2\) | ||
| 4 | 16 | \(n \le 200\,000\) | \(C \le 3\) | 3 | |
| 5 | 19 | \(n \le 10\,000\) | \(C \le 10^9\) | 0–2 | |
| 6 | 27 | \(n \le 500\,000\) | \(C \le 10^9\) | Offline-проверка | 0–5 |
5 7 6 3 4 10
2 3 4 2 1
7 1 1 1 2 2 1 1
5 5 3 2 2 3 4