76
правок
Изменения
→Оптимизация до O(n log log k)
Предположим, мы знаем такое приближение числа <tex>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.
Чтобы достичь нужной оценки, будем делить последовательность на блоки длины <tex>m</tex> блоков, кроме последнего, который может быть меньше, и обрабатывать каждый блок отдельно.
=== Деление на блоки===
