Codeforces Round 726 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие — это ограничения на $$$n$$$ и $$$k$$$. Вы можете делать взломы, только если все версии задачи решены.
У вас есть строка $$$s$$$, и вы можете выполнять над ней два типа операций:
Вы можете использовать каждую операцию любое количество раз (возможно, ни одного).
Ваша задача — найти лексикографически наименьшую строку длины ровно $$$k$$$, которую можно получить, выполнив эти операции над строкой $$$s$$$.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:
Первая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5\cdot 10^5$$$) — длину исходной строки $$$s$$$ и длину желаемой строки.
Вторая строка содержит строку $$$s$$$, состоящую из $$$n$$$ строчных английских букв.
Выведите лексикографически наименьшую строку длины $$$k$$$, которая может быть получена путем выполнения операций над строкой $$$s$$$.
8 16 dbcadabc
dbcadabcdbcadabc
4 5 abcd
aaaaa
В первом тесте оптимально сделать одно дублирование: «dbcadabc» $$$\to$$$ «dbcadabcdbcadabc».
Во втором тесте оптимально удалить последние $$$3$$$ символа, затем продублировать строку $$$3$$$ раза, затем удалить последние $$$3$$$ символов, чтобы строка имела длину $$$k$$$.
«abcd» $$$\to$$$ «abc» $$$\to$$$ «ab» $$$\to$$$ «a» $$$\to$$$ «aa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa».
Название |
---|