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

1. Персистентность, введение
1. Стек
2. Дерево отрезков → дерево отрезков
3. СНМ через персистентный массив (амортизация операций не работает)
4. Общая идея: любая структура состоит из массивов
5. Декартово дерево (treap) с операциями insert, delete
6. Проблема с merge с собой, RBST (treap без y)
7. Offline решение (дерево версий, откаты)


2. Сканирующая прямая и применение персистентности
1. Точка, покрытая максимальным числом прямоугольников
2. Количество пересекающихся вертикальных и горизонтальных отрезков
3. Площадь объединения прямоугольников
4. Сумма в прямоугольнике (а теперь в online за log)
5. Локализация точки в многоуогольнике, в планарном графе (объединяется с персистентностью)
6. Число различных на отрезке (и тоже в online за log)
7. Сколько точек в треугольнике? Стороны треугольника всегда горизонтальная, вертикальная, под 45. В online как обычно работает.
8. Даны 2D-точки, online запрос = полуплоскость с фиксированным углом α, сказать сколько точек в полуплоскости.
9. Scan-ray + persistent : даны n ≤ 1000, 2D-точек, online запрос = полуплоскость, сказать сколько точек в полуплоскости.
10. А если n ≤ 50 000, q ≤ 50 000?


3. k-я порядковая на отрезке за O(logn)


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