XS4 занятия
Параллель XS
Деревья и математика.
Занятие 1ДеревьяДвоичные подъёмы и LCA, разреженная таблица, эйлеров обход и запросы на путях, алгоритмы Тарьяна, подъёмы с линейной памятью, сжатое дерево, лесенки, метод четырёх русских, декартово дерево.≈ 4,5 чЗанятие 2SQRT-декомпозицияРазбор контеста по деревьям, корневая декомпозиция и алгоритм Мо (на массиве, на дереве, с изменениями), тяжёлые и лёгкие вершины, корневая по запросам: связность, ближайшая чёрная клетка, минимальный остов, перебор значений ⌊x / i⌋.≈ 5 чЗанятие 4Математика 1Разбор контеста по строкам и дистанционного тура; решето Эратосфена и линейное решето, мультипликативные функции, теорема Эйлера, расширенный Евклид, китайская теорема, включения-исключения, биномиальные коэффициенты, числа Каталана.≈ 5 чЗанятие 5Структуры данных 1Лекция по дереву отрезков и родственным структурам: массовые операции, площадь объединения прямоугольников, Фенвик, дерево сортировок и каскадирование, доминирование в 3D и 4D; разбор математики; семинар.≈ 4 ч 57 мин