codeofthrone's blog

Accesing multiset by indexing
By codeofthrone, history, 4 years ago, In English

In each query, I have to insert x in a vector so that it remains sorted and output the Yth element. Inserting was taking O(n) time.

I switched to multiset as it remains sorted on each insertion with O(log(n)) time but I am stuck in finding the Yth element. The only approach worked was to traverse the multiset from starting but again it gives TLE.

I searched the internet but couldn't found anything relevant. Is there any way to access the ith indexed element in multiset in O(log(n) ) time.

Consider I am using C++.

Thanks in advance.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Yes, there is. Checkout policy based data structures. Checkout these links

Odered_set PBDS

Blog by adamant

You can access it yth elemen in logn time using find_by_order(y).

You can convert it from a set to multiset, as you give it a comparator as less, instead give it less_equal. 

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;
→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

you can use lower_bound in multiset ,it will give iterator to the position of y in O(logn)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You still can't get the ith element using lower_bound, it simply gives the element just smaller than the given element.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Yeah, but we can check for it easily if it matches or not .

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What if we don't know the contents. to know the ith element , we must know what to pass in the lower_bound. right?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah actually you are right ,we must know what to pass in the lower_bound. policy based data structure is there for this purpose :)

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You want to find the y-th element, not ‘an iterator to the position of y’. How is this upvoted?

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

nvm it Works

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I keep duplicate element and want to erase an element from pbds then erase function does't work. Is there any solution?? Thanks in advance.

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

    Suppose you want to erase num then, auto temp = mySet.find_by_order(num);

    mySet.erase(temp);

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

works with me: https://codeforces.me/blog/entry/11080?#comment-258244

→ Reply