Как использовать дерево сегментов и сканлайн

Question

Дано 300000 сегментов. Рассмотрим любую пару сегментов: a = [l1,r1] а также b = [l2,r2], Если l2 >= l1 а также r2 <= r1 Это "хорошая" пара. Если a == bЭто "плохая" пара. Сверхурочно, это "плохая" пара.

Как найти количество всех "хороших" пар среди заданных сегментов, используя дерево сегментов и сканлайн?

Answer 1

Сортируйте сегменты в возрастающем порядке по их l-значениям, а для пар с одинаковыми l-значениями сортируйте их по убыванию по их r-значению.

Предположим, для конкретного случая вы хотите посчитать количество хороших пар (ai,aj) таким, что j

Переходя к части дерева сегментов, строим дерево сегментов по значениям r. При обновлении значения r в дереве сегментов добавьте 1 к значению r в дереве сегментов и для запроса определенного значения r запросите сумму в диапазоне [0,r-1]. Это даст общее количество сегментов, которые хорошо подходят для данного сегмента.

Если значения r большие, которые не вписываются в дерево сегментов, то сначала примените сжатие координат к значениям, а затем используйте дерево сегментов для сжатых значений.