C++ with SegmentTree
Intuition\nThe solution needs to O(nlgn). Can\'t use BSTree because it can become skewed - and worst case complexity is O(n^2)\n\nWe basically need to find the 
# Intuition\nThe solution needs to $$O(nlgn)$$. Can\'t use BSTree because it can become skewed - and worst case complexity is $$O(n^2)$$\n\nWe basically need to find the value of `greaterCount()` in $$O(lgn)$$\n\nIf the array is sorted, one way to find `greaterCount(num)` is to find the count of numbers starting from the `upper_bound(num)`\n\n# Approach\n  * Use Segment Tree to store the sorted `nums[]`\n  * For numbers that are repeated, SegmentTree can store the count.\n  * No need to store the actual number. Only store the count for each index. Where `index` is the index of the number in the sorted vector.\n\nTake the case:\n`[5,14,3,1,5,2,3]`\n\nThe sorted vector (removing repetition):\n`[1, 2, 3, 5, 14]`\n\nNow if in the SegmentTree, we store the count (at any point):\n`[1 : 1, 2 : 1, 3 : 2, 5 : 2, 14 : 1]`\n\n`greaterCount(num)` in the context of the SegmentTree can simply be defined as: sum of count for `[pos(num) + 1, end]`\n\n# Complexity\n- Time complexity: $$O(nlgn)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\n    class SegmentTree {\n      private:\n        int n;\n        vector<int> t;\n      public:\n        SegmentTree(int n) {\n            this->n = n;\n            t = vector<int>(n * 4, 0);\n        }\n        int find(int range_index, int start, int end, int pos) {\n            if (end < pos) {\n                return 0;\n            }\n\n            if (start >= pos) {\n                return t[range_index];\n            }\n\n            int mid = (start + end) / 2;\n            return\n              find(2 * range_index + 1, start, mid, pos) +\n              find(2 * range_index + 2, mid + 1, end, pos);\n        }\n        void update(int range_index, int start, int end, int pos) {\n            if (start > pos || end < pos) {\n                return;\n            }\n\n            if (start == end) {\n                t[range_index]++;\n                return;\n            }\n\n            int mid = (start + end) / 2;\n            update(2 * range_index + 1, start, mid, pos);\n            update(2 * range_index + 2, mid+1, end, pos);\n\n            t[range_index]++;\n        }\n    };\n\n    vector<int> get_sorted_vector(const vector<int>& nums) {\n        set<int> nums_sorted_unique(nums.begin(), nums.end());\n        return vector<int>(nums_sorted_unique.begin(), nums_sorted_unique.end());\n    }\n\n    int get_num_index(const vector<int>& sorted_nums, int num) {\n        return lower_bound(sorted_nums.begin(), sorted_nums.end(), num) - sorted_nums.begin();\n    }\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> nums_sorted_unique = get_sorted_vector(nums);\n        int num_unique = nums_sorted_unique.size();\n\n        SegmentTree st1(num_unique), st2(num_unique);\n        vector<int> arr1, arr2;\n\n        arr1.push_back(nums[0]);\n        st1.update(0, 0, num_unique - 1, get_num_index(nums_sorted_unique, nums[0]));\n        arr2.push_back(nums[1]);\n        st2.update(0, 0, num_unique - 1, get_num_index(nums_sorted_unique, nums[1]));\n\n        for (int i = 2; i < nums.size(); i++) {\n            int num = nums[i];\n            int num_pos = get_num_index(nums_sorted_unique, num);\n            // num_pos + 1, is the first index for the numbers > num (in the sorted array)\n            // aka upper_bound\n            int gc1 = st1.find(0, 0, num_unique - 1, num_pos + 1);\n            int gc2 = st2.find(0, 0, num_unique - 1, num_pos + 1);\n\n            int dest = 1;\n\n            if (gc1 != gc2) {\n                dest = gc1 > gc2 ? 1 : 2;\n            } else if (arr1.size() != arr2.size()) {\n                dest = arr1.size() < arr2.size() ? 1 : 2;\n            }\n\n            if (dest == 1) {\n                arr1.push_back(num);\n                st1.update(0, 0, num_unique - 1, num_pos);\n            } else {\n                arr2.push_back(num);\n                st2.update(0, 0, num_unique - 1, num_pos);\n            }\n        }\n\n        // Append (arr2) at the end of (arr1) and return.\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n\n```
['C++']