Занятие 1Применение дерева отрезковОрганизация параллели X; подсчёт на отрезке, персистентное дерево отрезков, число различных, MEX, k-я статистика на отрезке и на пути, disjoint sparse table, дерево отрезков без push.≈ 1 ч 45 минЗанятие 2Теория чиселРазбор контеста по дереву отрезков; алгоритм Евклида, дерево Штерна—Броко, геометрия решёток, рациональная реконструкция, floor sum, решёта, мультипликативные функции, НОД-свёртки.≈ 4 ч 08 минЗанятие 3Суффиксные структуры 1Тандемные повторы через Z-функцию, минимальный циклический сдвиг за O(n), суффиксный массив и LCP-массив (алгоритм Касаи), применения: число различных подстрок, поиск паттерна бинпоиском, наибольшая общая подстрока двух строк, построение суффиксного массива за O(n log n).≈ 1 ч 36 минЗанятие 4Введение в потокиРазбор задач на суффиксный массив и лекция про потоки: максимальный поток и минимальный разрез, алгоритмы Форда—Фалкерсона, Эдмонса—Карпа и Диница, паросочетания, гаджеты для разрезов.≈ 2 ч 40 минЗанятие 5Корневые эвристикиРазбор контеста по потокам и разрезам; тяжёлые и лёгкие вершины, рюкзак с корневой оценкой, блочные структуры, алгоритм Мо и его варианты, прямоугольник с нулевой суммой.≈ 4 ч 10 мин