На чём держится
дерево отрезков
Статьи
DS
Структура данных
Дерево отрезков
Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n).
O(log n) на запрос и на изменение
2 задачи
GRA
Алгоритм
Тяжёлые пути
Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков.
O(log² n) на запрос
1 задача
DP
Приём
Convex hull trick
Минимум прямых вместо перебора: 1776 тестов каталога по запускам песочницы — и квадратичная динамика становится линейной.
O(n)
2 задачи
GEO
Приём
Заметающая прямая
Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей.
O((n + k) log n)
3 задачи
Задачи
Часто рядом
олимпиады 3 запросы на отрезке 2 дерево 2 наука и физика 2 геоданные 2 разделяй и властвуй 1 рекурсия 1 массив 1 аналитика 1 классика 1 граф 1 динамика 1