Tareq_Ali's blog

Multi Ordered Set Data Structure
By Tareq_Ali, history, 4 years ago, In English

Hello everyone

I would like to share with you an efficient trick we can use with ordered_set data structure to make it contain more than one occurrence for any value we want without any problem. But first, if you don't know this data structure, you can read about it here .

Now let's discuss that:

First of all, for sure we need to set the comparison operator to $$$\textbf{" less_equal <data_type> "}$$$ to allow occurrences, after that insertion will work fine, but the function erase will do nothing ever.

I noticed that using the comparison operator $$$\textbf{" less_equal <data_type> "}$$$ makes the two functions $$$\textbf{" s.lower_bound(value) , s.upper_bound(value) "}$$$ exchange their functions for any value, depending on that to erase one occurrence of some value from the set we can write $$$\textbf{" s.erase(s.upper_bound(value)) "}$$$, just that simple, it will work efficiently.

To see the important functions of this data structure you can read my code, I have tested the code and got accepted in many problems. for example, this is the problem, and this is my submission.

About time and space complexity:

Time complexity is $$$\textbf{O( log2(N) )}$$$ for each operation.

Space complexity is less than double the space complexity of the general $$$\textbf{STL set}$$$ for reasonable cases ( N <= 10000000 ).

Some people use an ordered_set of pairs to count occurrences in $$$\textbf{" p.second "}$$$ and do the job, But this is faster to code and can do more tasks, Suppose you have an empty set and 2 types of queries:

  • inserting the element (x) into the set.

  • answering this query : what is the k_th element in the set if we sort the elements in ascending order.

Now if you use it this way, you can answer the query in 1 line of code, and the pair trick can't solve it.

Finally, thank you for reading my first blog, I hope it will be benefit <3 .

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

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

If I'm not mistaken, s.erase(--s.lower_bound(value)) also works. Would be nice if someone confirmed.

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

    Yes for sure it will work, but be careful in case of "value" is not in the set in order not to erase any other element.

    → Reply
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Glad, I have come across this post. Otherwise i would have cursed the ordered set for not working. Thanks for the help :)

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

Noobs using pbds, gods writing treap.

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

    Since I haven't ever heard about Treap data structure, and since it seems that you are a god, maybe I will read about it to know how a god feels.

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

int Count(ordered_set &s,int x){ //this function returns the number of occurrences of the value (x).

if(!Exist(s,x)){
    return 0;
 }
 return LastIdx(s,x)-FirstIdx(s,x)+1;

} what is the complexity of this function ?? because in the set we can only use distance(ptr,pointer) but it take O(n).

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

    It is "log2(n)" bro, and to be very specific it is not only "log2(n)" but a bit more like "3 * log2(n)" which we can say that it is "log2(n)".

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

Can any one tell me. Why I am getting tle. D. Pashmak and Parmida's problem using ordered multiset.

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

    Ordered set is too slow, try doing it with Fenwick/Segment tree

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Thanks, I have done with Fenwick tree. With the ordered set why did it not pass as n=1e6 if the set has all operations in log2(n)?

      Is there too much tight bound in the problem because one of my submissions 192035586 got tle due to query l to r and one 192038110 got Ac with direct sum query?

      If yes then how do you handle these tight bound in the contest I know my solution is right but submitting code with a minor change, again and again, give me -50 if WA.

      → Reply