Given an array of pairs $$$p[]$$$ of length $$$n(\leq 100000)$$$ I want to do the following:
Task 1: Given $$$q(\leq 100000)$$$ queries and $$$L,R,(pair\ p)$$$, output the number of pairs < p in the range $$$[L,R]$$$.
Task 2: Count the number of inversions in it. I can do inversions += query(i+1,n,p[i]) (if answer to Task 1 is available).
Task 3: Same as Task 1, but $$$L=1,R=n$$$ always. Can we directly use lower_bound for pairs < operator somehow?
< operator for pairs is defined as follows:- < (p1,p2){ return p1.F<p2.F && p1.S<p2.S;}
I know that we can do Task 1 for integers using a mergeSort-Tree, but how to do it for pairs?
Please let me know if there is an easier solution for Task 2 or Task 3 separately having an easier/direct implementation or smaller Time Complexity.
Pretty sure that task 1 can be solved using merge sort tree.
You can also use lower_bound function normally if you have an array of pairs:
Usual lower_bound won't work here. Please note, my operator definition of
< operator. I want both the .first and .second of pair to be less than the other.Lower bound will just check them based on .first and if they are equal, then only check for the .second.
Example:- $$$a=[(0,0),(1,2),(2,1)]$$$
I want
lower_bound({2,1})to return 1, but instead as per your solution it will return 2.Also, how can we use merge-Sort tree in case of pairs ? Please provide link for Task 1 is you saw it somewhere.
Your definition to operator < do not allow us to do a proper sort on the array, so I think it'll be difficulty to find an efficient solution.
Ex: