Ordered Set || Simple Solution
About Ordered Set\nIt performs all the operations as performed by the set data structure in STL in log(n) complexity and performs two additional operations also
# About Ordered Set\nIt performs all the operations as performed by the set data structure in STL in log(n) complexity and performs two additional operations also in log(n) complexity.\n\n```\norder_of_key (k) : number of items strictly smaller than k.\nfind_by_order(k) : K-th element in a set (counting from zero).\n```\nHere, I am using an ordered set which stores elements in reversed order, thus the function `order_of_key(k)` gives the number of elements strictly greater than k.\n\n# Comparison Predicates in Ordered Set\ngreater: This comparison predicate is used to order elements in descending order. In this case, when you insert elements into the ordered_set, they will be stored in descending order of their values.\n\ngreater_equal: This comparison predicate is used to order elements in non-strictly descending order. It means that elements with equal values will not be considered equivalent and will be stored in the order they were inserted.\n\nless: This comparison predicate is used to order elements in ascending order. In this case, when you insert elements into the ordered_set, they will be stored in ascending order of their values.\n\nless_equal: This comparison predicate is used to order elements in non-strictly ascending order. It means that elements with equal values will not be considered equivalent and will be stored in the order they were inserted.\n\n# Intuition\nSince the task was to calculate the number of elements that are strictly greater than a particular value, using ordered set would be the perfect approach.\n\n# Approach\n1. We need two vectors arr1, arr2 to push numbers. Each vector has a ordered set to count the values in that vector.\n2. Push the nums[0] to arr1, and nums[1] to arr2. Of course, insert them to the associated ordered set.\n3. Iterate through remaining numbers. Check conditions mentioned in the problems by using the `order_of_key()` function. Insert that number to arr1 or arr2 based on the conditions.\n5. Concatenate arr1 and arr2\n\n# Complexity\n- Time complexity: `O(N log N)`\n- Space complexity: `O(N)`\n\n# Code\n```\n#include <ext/pb_ds/assoc_container.hpp>\n#include <ext/pb_ds/tree_policy.hpp>\nusing namespace __gnu_pbds;\ntypedef tree<int, null_type, greater_equal<int>, rb_tree_tag,\n             tree_order_statistics_node_update>\n    oset;\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        oset o1, o2;\n        vector<int> arr1, arr2;\n        o1.insert(nums[0]);\n        o2.insert(nums[1]);\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        for (int i = 2; i < nums.size(); i++) {\n            int val = nums[i];\n            int a = o1.order_of_key(val), b = o2.order_of_key(val);\n            if (a > b) {\n                o1.insert(val);\n                arr1.push_back(val);\n            } else if (a < b) {\n                o2.insert(val);\n                arr2.push_back(val);\n            } else {\n                if (o2.size() < o1.size()) {\n                    o2.insert(val);\n                    arr2.push_back(val);\n                } else {\n                    o1.insert(val);\n                    arr1.push_back(val);\n                }\n            }\n        }\n        for (int i : arr2)\n            arr1.push_back(i);\n        return arr1;\n    }\n};\n```
['Ordered Set', 'C++']