Codeforces 100971.J

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

Комментарии

Пусть 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 \times; log^2(n)).