Даны 300000 сегментов. Рассмотрим любую пару сегментов: a = [l1,r1] и b = [l2,r2]. Если l2 >= l1 и r2 <= r1 , то это "хорошая" пара. Если a == b, то это "плохая" пара. Более того, это «плохая» пара.
Как найти количество всех «хороших» пар среди заданных сегментов, используя дерево сегментов и строку сканирования?
Отсортируйте сегменты в порядке возрастания относительно их значений 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 велики и не помещаются в дерево сегментов, то сначала примените сжатие координат к значениям, а затем используйте дерево сегментов для сжатых значений.
