Блог пользователя AM_I_Learning

Doubt on this general query based question.
Автор AM_I_Learning, история, 6 лет назад, По-английски

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.

Problem Link :-Codechef Bulbs

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

Please help . Thanks in advance.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I never got why the hell you all keep calling questions "doubt". I doubt you even know the meaning of that word.

→ Ответить
»
6 лет назад, скрыть # |
← 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 \gt x}$$$ and $$${arr[l].a \lt =x}$$$. Then query for count of values <= $$${y}$$$ in range $$$[1,l]$$$ using merge sort tree.

→ Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Divide and Conquer passes but barely: https://www.codechef.com/viewsolution/30575723

→ Ответить