Как найти площадь прямоугольников с учётом пересечений (объединение прямоугольников) за O(n log n)

Задача: На плоскости есть много прямоугольников. Их стороны параллельны осям координат. Нужно посчитать занимаемую ими площадь. Так же нужно учитывать то что они пересекаются. И всё бы хорошо, только прямоугольников целых 100000, а их координаты достигают 10^14 (ага, и размеры ~10^18)!

Я придумал только такое решение:
Используем метод сканирующей прямой. Сортируем по x все вертикальные стороны. Проходимся по ним, и соответственно формула при переходе прямой такая:
S_new = DELTA_X * active_ys;
Где DELTA_X - насколько переместилась сканирующая прямая, а active_ys - суммарная высота пересекающих линию прямоугольников.
И проблема как раз таки в вычислении этого active_ys. Можно сохранять все высоты прямоугольников как отрезки, и потом их складывать с учётом пересечений, но у меня это получается только за O(Y) (где Y - кол-во отрезков), и сложность всего алгоритма получается O(NY), а т.к. в худшем случае Y = N, то выходит O(N^2), что разумеется очень плохо. Можно было бы хранить все точки по y, но учитывая ограничения по координатам (10^14) ни в какую память это не влезет. Еще была идея хранить в дереве отрезков все эти отрезки, но непонятно как их суммировать, т.к. они ведь могут и не пересекаться, и задача по сути вернётся к исходной. К тому же эти отрезки надо ещё и удалять.

Может кто-то знает как можно решить эту задачку хотя бы за O(n log n)?