Codeforces 100971.M

Ссылка на задачу

• Codeforces #100971.M — Разбиение на хорошие строки

Комментарии

Пусть d[i] — минимальное количество хороших строк, на которые можно разбить префикс s[0]..s[i].

Если s[0]..s[i] содержит ровно k различных букв, то d[i] = 1.

Иначе найдём такое минимальное l <= i и максимальное r <= i, что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).

Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn).

Подсчёт количества различных букв на отрезке можно осуществлять:

• 26 бинарными поисками за O(26 × logn);
• деревом отрезков отсортированных массивов за O(log^2(n));
• деревом отрезков битовых масок за O(log^2(n)) (лишний логарифм на подсчёт числа единиц в результирующей маске);
• разреженной таблицей битовых масок за O(logn).

Определение l и r можно осуществлять:

• бинарным поиском за O(logn);
• двумя указателями за O(1*).

Принимаются решения с итоговой асимптотикой не хуже O(n × log^2(n)).