### AM_I_Learning's blog

By AM_I_Learning, history, 6 months ago,

We have to handle Q queries on the array and in each query we are asked to find number of pairs {a,b} present at the moment in the array whose value are such that a<=x and b<=y for {x,y} given in the query.

Please share the approach as I am not getting any tutorial for this problem

• 0

 » 6 months ago, # |   0 I never got why the hell you all keep calling questions "doubt". I doubt you even know the meaning of that word.
•  » » 6 months ago, # ^ |   -8 My English is very poor sorry!!!
•  » » » 6 months ago, # ^ |   0 It's not really "your" English, I have seen tons of posts using the "doubt" word like this too. Just can't stand it anymore right now.
•  » » » » 6 months ago, # ^ |   0 leave about the doubt etc.... can you explain how to solve the question in the link provided to me. I just wanted to know the approach as I am stuck from past 10 days.
 » 6 months ago, # | ← Rev. 4 →   +1 Sort the array initially. The array will be sorted by {a}. Then build a merge sort tree over this array using {b} values. You can perform any query in ${O(logn)}$ by performing a binary-search to find a ${l}$ in the array such that ${arr[l+1].a > x}$ and ${arr[l].a<=x}$. Then query for count of values <= ${y}$ in range $[1,l]$ using merge sort tree.
 » 6 months ago, # |   +1 Divide and Conquer passes but barely: https://www.codechef.com/viewsolution/30575723
•  » » 6 months ago, # ^ |   0 Can you write the algorithm or the pseudocode it will be really helpful!!!
•  » » » 6 months ago, # ^ |   +1 Check out this link and this. The first problem on the second link is exactly this problem.
•  » » » » 6 months ago, # ^ |   0 thank you so much