shailesh_24's blog

By shailesh_24, history, 11 months ago, In English,

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+1)).

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..!!

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shailesh_24 (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you don't require updates you can do it in O(log(MAX)) by using persistent segment trees covering the range [1, MAX] and giving the frequency to each value.

If you do require updates you can do it in O(log^2(n)) by using a normal segment tree that has an order statistics set in each segment. Counting frequency of X is just order_of_key(X+1) — order_of_key(X).

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    itu Counting frequency of X is just order_of_key(X+1) — order_of_key(X). could you please elaborate it more..??

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I'm talking about the order statistics set data structure. You can implement it with a binary search tree where each node knows how many nodes there are in its subtree. It's basically the structure that directly solves this problem: http://www.spoj.com/problems/ORDERSET/ (though you can solve this problem easily offline).

      For implementation details, you can use a treap instead of avl/red-black, or you can use the GNU version: http://codeforces.com/blog/entry/11080

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I understood your query part but how to update in such a segment tree considering I am dealing with range updates (adding x from l to r).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would do something simpler like sqrt decomposition in such a case, if there's enough time.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

use persistent range tree which is built by value.

u need to lazy create it i think.

sounds

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To be more specificly,

    Spoiler!

    If it is wrong plz figure it out and that would be appreciate :)