Suppose , we have a list of N pairs of the form ( Ai , Bi ) , and number of queries Q, where in each query, a number is given ( say X ) and we have to calculate the number of pairs , where X lies in between ( Ai and Bi ).
Now , if we sort the list of n pairs , then for a particular query we can easily find the range starting from index 1 to ith index using lower/upper bound , where for every jth index 1 <= j <= i
( Aj <= X ) , means only in this range , it is possible that X lies in between (Aj and Bj ).
Now, I want to know how can we determine the number of Bj’s such that 1 <= j <= i and Bj >= X , ( which is equivalent to our answer ) in log(n) time , we can’t use upper/lower bound , because they may be sorted or not.
1 <= N , Q <= 100000
1 <= Ai , Bi , X <= 1000000000000000