C++ Segment Tree solution. O(nlogn)
Approach\n Describe your approach to solving the problem. \nSegment tree with single point update.\n\n# Code\n\nclass SegTree {\n  public:\n    SegTree() {\n   
# Approach\n<!-- Describe your approach to solving the problem. -->\nSegment tree with single point update.\n\n# Code\n```\nclass SegTree {\n  public:\n    SegTree() {\n        for (int i = 0; i < 400030; i++)\n            data_[i] = 0;\n    }\n\n    int query(int low) {\n        return query(low, n_, 0, n_, 0);\n    }\n\n    void update(int n) {\n        update(n, 0, n_, 0);\n    }\n\n  private:\n    int query(int qlow, int qhigh, int low, int high, int i) {\n        if (low >= qlow && high <= qhigh) return data_[i];\n        if (low > qhigh || high < qlow) return 0;\n        if (low == high) return data_[i];\n        int mid = (low + high) / 2;\n\n        return query(qlow, qhigh, low, mid, (i << 1) + 1)\n                + query(qlow, qhigh, mid + 1, high, (i << 1) + 2);\n    }\n\n    void update(int n, int low, int high, int i) {\n        if (n < low || n > high) return;\n        data_[i]++;\n\n        if (low == high) return;\n\n        int mid = (low + high) / 2;\n        update(n, low, mid, (i << 1) + 1);\n        update(n, mid + 1, high, (i << 1) + 2);\n    }\n\n    int n_ = 100000;\n    int data_[400030];\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> nums_cp(nums.begin(), nums.end());\n        sort(nums_cp.begin(), nums_cp.end());\n\n        unordered_map<int, int> num_map;\n        int id = 0;\n        for (int i = 0; i < nums_cp.size(); i++) {\n            if (num_map.find(nums_cp[i]) == num_map.end())\n                num_map[nums_cp[i]] = id++;\n        }\n\n        vector<int> v1, v2;\n        SegTree t1, t2;\n\n        v1.push_back(nums[0]);\n        v2.push_back(nums[1]);\n        t1.update(num_map[nums[0]]);\n        t2.update(num_map[nums[1]]);\n\n        for (int i = 2; i < nums.size(); i++) {\n            int gc1 = t1.query(num_map[nums[i]] + 1);\n            int gc2 = t2.query(num_map[nums[i]] + 1);\n\n            if (gc1 == gc2) {\n                if (v1.size() <= v2.size()) {\n                    v1.push_back(nums[i]);\n                    t1.update(num_map[nums[i]]);\n                } else {\n                    v2.push_back(nums[i]);\n                    t2.update(num_map[nums[i]]);\n                }\n            } else if (gc1 > gc2) {\n                v1.push_back(nums[i]);\n                t1.update(num_map[nums[i]]);\n            } else {\n                v2.push_back(nums[i]);\n                t2.update(num_map[nums[i]]);\n            }\n        }\n\n        v1.insert(v1.end(), v2.begin(), v2.end());\n        return v1;\n    }\n};\n```
['C++']