$ ЛКШ 2018, 2-й день, Persistent World (Даниил Николенко)

# Персистентность, введение
## Стек
## Дерево отрезков &rarr; дерево отрезков
## СНМ через персистентный массив (амортизация операций не работает)
## Общая идея: любая структура состоит из массивов
## Декартово дерево (treap) с операциями insert, delete
## Проблема с merge с собой, RBST (treap без y)
## Offline решение (дерево версий, откаты)

<br>
# Сканирующая прямая и применение персистентности
## Точка, покрытая максимальным числом прямоугольников
## Количество пересекающихся вертикальных и горизонтальных отрезков
## Площадь объединения прямоугольников
## Сумма в прямоугольнике (а теперь в online за log)
## Локализация точки в многоуогольнике, в планарном графе (объединяется с персистентностью)
## Число различных на отрезке (и тоже в online за log)
## Сколько точек в треугольнике? Стороны треугольника всегда горизонтальная, вертикальная, под 45. В online как обычно работает.
## Даны 2D-точки, online запрос = полуплоскость с фиксированным углом &alpha;, сказать сколько точек в полуплоскости.
## Scan-ray + persistent : даны n &le; 1000, 2D-точек, online запрос = полуплоскость, сказать сколько точек в полуплоскости.
## А если n &le; 50 000, q &le; 50 000?

<br>
# k-я порядковая на отрезке за O(logn)

<br>
# Продвинутая персистентность
## Очередь с минимумом и дек с минимумом за O(1)
## Убираем амотизацию, получаем персистентную очередь с минимумом за O(1)
## Что это ещё даёт: избавление от амортизации в векторе (удвоение), в хеш-таблице (только удвоение)
