Задачник Базовый курс EN

Как устроен

офлайн-запросы

Статьи

DS Приём Корневая декомпозиция Блоки по √n: целые отвечают сразу, разрезанные — поклеточно; O(√n) там, где дерево отрезков не складывается. И порядок Мо. O(√n) на запрос; Мо — O(n√q) на все 1 задача DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи

Задачи

Аэропорты открываются Тёмные острова Перекрытия улиц Сколько людей в прямоугольнике Высота без дерева Кэш любого размера

Часто рядом

классика 3 олимпиады 3 запросы на отрезке 2 система непересекающихся множеств 2 дерево 2 массив 2 наука и физика 2 разделяй и властвуй 1 связность 1 амортизация 1 карты и навигация 1 изображения 1