Ну, вроде можно деревом отрезков:
Храним в каждой вершине помимо ответа количество отрезков с левой границей в соотв. вершине отрезке и с правой границей в каждом из соседних справа отрезках.
Получать ответ так: ответ в левом ребёнке + ответ в правом ребёнке + количество отрезков с левой границей в левом ребёнке и правой границей в правом ребёнке (это, кажется, можно посчитать рекурсивно).

Как ты из этого ответ для произвольного отрезка получаешь?

Мб можно и проще, но вот это должно работать.

Отрезок [L, R] лежит в отрезке [X, Y] если X <= L && R <= Y
Это стандартный запрос на прямоугольнике, вида "дана точка, сколько точек лежат правее и ниже?" (мы ставим отрезку [A, B] точку с координатами (A, B))
Отвечать на запросы к прямоугольникам онлайн можно, например, построив лес персистентных ДО (одно на каждый горизонтальный уровень, которое для каждой вертикальной полосы хранит количество точек в этой полосе, ниже этого уровня)

Ну, вроде можно деревом отрезков:
Храним в каждой вершине помимо ответа количество отрезков с левой границей в соотв. вершине отрезке и с правой границей в каждом из соседних справа отрезках.
Получать ответ так: ответ в левом ребёнке + ответ в правом ребёнке + количество отрезков с левой границей в левом ребёнке и правой границей в правом ребёнке (это, кажется, можно посчитать рекурсивно).

А отрезки с правой границей из правого ребёнка могут же иметь левую границу дальше, чем левая граница текущей вершины ДО и тогда что с ответом? Или я не понял как пересчитывать?

Можно еще за log^2 c добавлением отрезков совсем тупо: в вершине ДО храним концы всех вершин, начинающихся в пределах данной, к примеру, в дерамиде. Теперь спускаемся в какую-то конечную вершину и проверяем сколько вершин находится слева

Тогда красивее получается жто решение

wtf

фу, ДД

Чем дд плохо?