74
правки
Изменения
м
Нет описания правки
Нам потребуется две структуры данных.
Во-первых, мы будем хранить очередь событий <tex>Q</tex> в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за <tex>O(\log{m})</tex>, где <tex>m</tex> {{---}} количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.
Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.
