Frequency of a number in the given range.....[L,R]

Правка en3, от shailesh_24, 2017-06-08 05:35:27

I tried to solve this question but suddenly a question strike to my mind what if we have to find the value of ONLY F(L,R,X) L and R are the indexes of the array and X=The element whose frequency we have to determined . one solution which strike to me is like..just take map< long long,vector >mp,and for each element of the given array just insert its corresponding index at that location for example if arr[]=[2,3,4,5,2,2].So mp[2]={0,5,6},mp[3]={3},mp[4]={2} and so on... and just take lower bound and upper bound of the value of L and R in mp[x]. So it will give us answer in NO of Query * O(log(abs(R-L)).

But Can some one please suggest me how can i can calculate ONLY F(L,R,X) by using SEGMENT TREE Proble Link.....

Thanks In Advance..!!

Теги divide and conquer, segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский shailesh_24 2017-06-08 20:33:43 2 Tiny change: 'og(abs(R-L)).\n\nBut' -> 'og(abs(R-L+1)).\n\nBut'
en3 Английский shailesh_24 2017-06-08 05:35:27 96
en2 Английский shailesh_24 2017-06-08 05:31:25 2 Tiny change: 'h element fo the given' -> 'h element of the given'
en1 Английский shailesh_24 2017-06-08 05:29:39 771 Initial revision (published)