So, I came across a problem that has a subtask of finding all the pairs (from a given set of pairs), whose first and second values are greater than the corresponding first and second values of a given pair. For example : we have a set of pairs s = {{2,3},{4,5},{6,7}} and the given pair is {3,4}, now we have to return all the pairs whose first value is greater than 3 and second value is greater than 4. It is evident that {4,5} and {6,7} are the answers.

Initially I thought of using lower_bound()/upper_bound() functions. But unfortunately, only one of the values (either first or second) will be taken care if we use it. Then @steveonalex told that we had to use segment tree to get the required answer. I don't know how to do it. So can someone explain how we can get the answer using segment tree?

I have an approach which seems fine at first but has a not so good time complexity (according to me). Approach : I will have a map whose keys are the first values of pair and their corresponding values to be a set/multiset of all the second values it has in the original set. For example: Given the set = {{1,2},{1,3},{1,4},{2,4},{2,5}} would have the map as m[1] = {2,3,4} m[2] = {4,5}

Now after these values are stored. I can directly do binary search to get the pointer/index of the set of each individual keys (the point from where the second value is greater).

The time complexity would be (log(N_1) + log(N_2) + log(N_3) ......). Where can N_1 + N_2 + .... = N. Is this right?

Can we do better than this? Please let me know.

How would I use these functions for pairs? I mean if I have a pair {a,b} and I would like a pair p = {c,d} such that a < c and b < d. The traditional lower_bound and upper_bound functions only give us a pair whose first value 'c' is greater or equal to 'a' and it doesn't care about b and d. Can I get the former in O(logN)?