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](https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/) .↵
↵
↵
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](https://ideone.com/oamEm8), I have tested the code and got accepted in many problems. for example, this is the [problem](https://mirror.codeforces.com/contest/652/problem/D), and this is my [submission](https://mirror.codeforces.com/contest/652/submission/108479892).↵
↵
↵
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 .
==================↵
↵
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](https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/) .↵
↵
↵
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](https://ideone.com/oamEm8), I have tested the code and got accepted in many problems. for example, this is the [problem](https://mirror.codeforces.com/contest/652/problem/D), and this is my [submission](https://mirror.codeforces.com/contest/652/submission/108479892).↵
↵
↵
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 .
