I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$
$a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis.
The question is how to find a algorithm that is strictly cheaper than $O(n^2)$ and it yields number of pairs $i,j$ such that $l_j$ completely contains $l_i$ and $j>i$.
I know that without the second constraint, we can just sort the segments by their starting points and do the inversion counting for the ending points.
However, if we want to satisfy the second constraint, what is the optimal way? I was thinking maybe I could maintain an augmented BBST and the key is just the starting point of each segment, once we insert a new segment, there may be some efficient way to count how many nodes in the tree have smaller ending points than the one I just insert.