Лекция: Sparse Table, binary lifting, бинарный поиск, задачи скачать в хорошем качестве

Лекция: Sparse Table, binary lifting, бинарный поиск, задачи

Сегодня мы собрались, чтобы разобраться, что такое Sparse Table и binary lifting. Попутно мы разобрали кучу задач (5-6), в которых можно применить Sparse Table, хоть и не обязательно это делать. Материалы занятия (задачи и исходники): https://docs.google.com/document/d/1u... 00:00:00 Введение 00:03:00 Что такое Sparse Table 00:09:00 Вычисление функции на отрезке за O(1) 00:11:03 Необходимая память O(n log(n)) 00:16:20 Максимальная степень двойки до n за O(1) с предподсчётом и без 00:20:50 Построение Sparse Table 00:24:26 Битовый сдвиг влево = степень двойки 00:27:40 Задача A. Ultra Sparse Table 00:32:30 Реализуем построение Sparse Table 00:37:00 Реализуем запрос к Sparse Table 00:39:30 Вопросы по числу операций за секунду 00:42:30 Задача: ближайший больший элемент 00:46:25 Бинарный поиск + Sparse Table 00:49:45 Ещё есть другое решение, за линию, со стэком 00:51:35 Вопросы про бинпоиск 00:52:20 Реализуем бинпоиск для Sparse Table 00:56:35 Задача F. Несбалансированный массив 01:05:25 Исходный код решения задачи 01:06:20 Как убрать (учесть) повторы из массива в этой задаче 01:11:15 Продолжаем разбирать исходный код задачи 01:14:30 Что такое лямбда-функции и компараторы 01:27:20 Binary lifting (двоичный спуск) 01:35:20 Реализация binary lifting на плюсах 01:41:30 Смотрим откуда задача взялась 01:43:20 Задача E. И снова карточная игра 01:46:00 Первое решение: теория чисел, факторизация, два указателя 01:52:45 Объясняю первое решение на пальцах (на примере) 01:55:30 Подрубаем метод двух указателей в первом решении 01:56:45 Второе решение: Sparse Table + binary lifting 02:04:45 Почему не работают префикс-произведения: модуль не простой 02:06:10 Вычисление функции за O(log(n)) из-за пересечений 02:09:20 Итоговая асимптотика второго решения 02:10:50 Смотрим исходный код решения 02:15:36 Реализация шаблонной функции для Sparse Table 02:19:20 Реализация шаблонной структуры Sparse Table 02:24:20 Задача C. Новогоднее дерево 02:24:40 Используем поиск минимума и его позиции 02:27:40 Строим дерево за квадрат 02:29:55 Ускоряем с помощью сортировки и Sparse Table 02:34:50 Вопрос: третье решение через LCA 02:39:10 Идея по двумерной Sparse Table в задаче L. OpenStreetMap 02:42:00 Вопрос: кто такой tourist? 02:45:30 Смотрим исходный код C. Новогоднее дерево 02:51:30 Прощаемся