Параллель А'

Страница на алгокоде

---

1. Корневая оптимизация

• Корневая декомпозиция на массиве
• Корневая на строках
• Корневая в задачах на графы
• split-rebuild
• split-merge
• Корневая по запросам
• Алгоритм Мо
• Рюкзак за $O(S \sqrt{S})$

2. Геометрия 1

• Векторы
• Прямые
• Отрезки
• Окружности
• Выпуклая оболочка
• Проверка точки на принадлежность многоугольнику за $O(n)$
• Локализация точки в выпуклом многоугольнике
• Касательные к многоугольнику
• Формула Пика
• Пересечение полуплоскостей

3. Структуры данных 1

• Дерево отрезков
• Декартово дерево
• Дерево Фенвика
• Merge sort tree
• Отложенные операции
• Динамические структуры данных
• Двумерные структуры данных

4. Оптимизации динамики

• Монотонность точки перегиба
• Divide&Conquer оптимизация
• Оптимизация Кнута
• Convex hull trick
• Дерево Li Chao
• Лямбда-оптимизация
• $\text{MOD}^2$-оптимизация

5. Математика 1

• Алгоритм Евклида
• Расширенный алгоритм Евклида
• Диофантово уравнение
• Обратный по модулю
• Решето Эратосфена
• Линейное решето Эратосфена
• Обратные ко всем остаткам за O(p)

6. Структуры данных 2

• RMQ offline с СНМ
• RMQ в окне
• Sparse Table
• Disjoint Sparse Table
• LCA
• $RMQ \pm 1$
• Эйлеров обход дерева
• Сжатые деревья
• Heavy-light decomposition

7. Структуры данных 3

• Centroid декомпозиция
• Переливания

8. Строки 1

• Z-функция
• Префикс-функция
• Алгоритм Манакера
• Тандемные повторы
• Бор
• Ахо-Корасик

9. Графы 1

• DFS
• BFS
• 0-1 BFS
• 0-K BFS
• Поиск мостов и точек сочленения
• Конденсация графа
• Топологическая сортировка
• 2-SAT

10. Битовые оптимизации

• Bitset
• Перебор всех подмасок данной маски
• Динамическое программирование по профилю
• Динамическое программирование по подмножествам
• Meet in the middle

11. Строки 2

• Хэши
• Суффиксный массив