Учитывая 300000 сегментов. Рассмотрим любую пару сегментов: a = [l1,r1] и b = [l2,r2]. Если l2 >= l1 и r2 <= r1, это «хорошая» пара. Если a == b, это «плохая» пара. Напротив, это «плохая» пара.Как использовать дерево сегментов и scanline
Как найти число всех «хороших» пар среди заданных сегментов с использованием дерева сегментов и строки сканирования?
Сортируйте сегменты в порядке возрастания относительно их значений l и для пар с одинаковыми l-значениями сортируйте их в порядке убывания по отношению к их r-значению.
Предположим, что для определенного вам нужно подсчитать количество хороших пар (ai, aj) таких, что j < i. Пусть ai = [l1, r1] и aj = [l2, r2]. Тогда имеем l2 < = l1. Теперь нам нужно рассчитать все возможные значения j такие, что r2 < = r1. Это можно сделать, поддерживая дерево сегментов для значений r для всех j таких, что 0 < j < i. После запроса для i-й пары обновите дерево сегментов с r-значением i-го сегмента.
Приступив к разделению части дерева, постройте дерево сегментов по значениям r. При обновлении значения r в дереве сегментов добавьте 1 к значению r в дереве сегментов и запросите конкретное значение r, запрос для суммы в диапазоне [0, r-1]. Это даст общее количество сегментов, которые соответствуют этому сегменту.
Если значения r являются большими, которые не вписываются в дерево сегментов, сначала примените координирование сжатия к значениям, а затем используйте дерево сегментов для сжатых значений.