Finding all the pairs whose individual values are more than a given pair

Revision en3, by PerryThePlaytypus, 2024-09-15 15:13:31

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 K*(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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English PerryThePlaytypus 2024-09-15 19:11:12 2 Tiny change: ' would be K*(log(N_1) ' -> ' would be (log(N_1) '
en3 English PerryThePlaytypus 2024-09-15 15:13:31 0 (published)
en2 English PerryThePlaytypus 2024-09-15 15:13:10 2 Tiny change: 'this right. \n\nCan ' -> 'this right? \n\nCan ' (saved to drafts)
en1 English PerryThePlaytypus 2024-09-15 11:40:27 1698 Initial revision (published)