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.
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.
very helpful , thanks
you can use lower_bound in multiset ,it will give iterator to the position of y in O(logn)
You still can't get the ith element using lower_bound, it simply gives the element just smaller than the given element.
Yeah, but we can check for it easily if it matches or not .
What if we don't know the contents. to know the ith element , we must know what to pass in the lower_bound. right?
yeah actually you are right ,we must know what to pass in the lower_bound. policy based data structure is there for this purpose :)
You want to find the y-th element, not ‘an iterator to the position of y’. How is this upvoted?
nvm it Works
reinstall gcc if that's true (which I highly doubt).
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.
Suppose you want to erase num then, auto temp = mySet.find_by_order(num);
mySet.erase(temp);
Thanks @Boring_Day