Merge_sort Tree MST(Revisited) Unofficial Editorial for Beautiful Pairs CODEMANIA

Problem link Contest problem link.

Quick explanation we want to calculate number of given pairs in the list which satisfy the constraints l1<=p1.first<=r1 and l2<=p2.second<=r2 where l2,r2 are given in the queries .

By looking in the problem it is very clear that in the first attempt we have to sort the array and want to get the range space to query for next set l2 and r2 at first we will query for l1 and r1 with plain binary search over the sorted array and we will get the upper and lower bound indices for applying our next search over the space since we sorted the vector of pairs earlier on the basis of first part of pair only so it is obvious the second part of all pairs are not sorted so we cant apply plain binary search so the problem after getting the range space gets converted to we have an array for second indices of pairs and this array is to be queried for the property that number of elements in this array in a particular range lies between l2 and r2 this is not at all easy it is difficult but can be implemented easily with merge sort trees . I have written a code and tested it it works fine any other approach is also welcomed .

YOU CAN GET THE MOTIVATION TO LEARN MERGE SORT TREES FOR THIS PROBLEM.

C++14 implementation
my solution

2 Likes

Link to learn merge sort trees nice explanation