Tree with Counters
This is a classic problem of counting smaller (larger) elements in a mutating container.\n\nSimilar problems:\n- 315. Count of Smaller Numbers After Self\n- 493
This is a classic problem of counting smaller (larger) elements in a mutating container.\n\nSimilar problems:\n- [315. Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76628/9-solutions-with-pictures-and-runtime-comparison)\n- [493. Reverse Pairs](https://leetcode.com/problems/reverse-pairs/discuss/97322/C%2B%2B-Self-ballancing-BST-with-counters)\n\n> Brute-force quadratic solutions are accepted for this problem due to weak test cases and higher runtime limits.\n \nFor counting larger elements, we can use BST, or, with value compression, a segment or Fenwick (BIT) tree.\n\nThe standard BST implementation (map or set) won\'t help us: while we can find the insertion point in a logarithmic time, counting smaller/larger elements will still take a linear time.\n\nInstead, we use a custom BST implementation that tracks the statistic (number of elements on the left/right) for each node.\n\n> Note that we need to also balance the tree as we populate it to maintain logarithmic search time (avoid "vines").\n\n**C++**\n```cpp\ntemplate<class T> class TreeNodeWithCounter {\n    T val;\n    TreeNodeWithCounter *left = nullptr, *right = nullptr;\n    int cnt_left = 0, cnt_right = 0, cnt_val = 1;\npublic:\n    ~TreeNodeWithCounter() { delete left; delete right; }\n    TreeNodeWithCounter(T v) : val(v) {};\n    void insert(T v, TreeNodeWithCounter **thisNode) {\n        if (v == val) \n            ++cnt_val;\n        else if (v < val) {\n            ++cnt_left;\n            if (left == nullptr)\n                left = new TreeNodeWithCounter(v);\n            else \n                left->insert(v, &left);\n        }\n        else {\n            ++cnt_right;\n            if (right == nullptr)\n                right = new TreeNodeWithCounter(v);\n            else\n                right->insert(v, &right);\n        }\n        if (cnt_left > cnt_right + 2) { // right rotation\n            *thisNode = left;\n            left = left->right;\n            (*thisNode)->right = this;\n            this->cnt_left = (*thisNode)->cnt_right;\n            (*thisNode)->cnt_right += this->cnt_val + this->cnt_right;\n        }\n        else if (cnt_left + 2 < cnt_right) { // left rotation\n            *thisNode = right;\n            right = right->left;\n            (*thisNode)->left = this;\n            this->cnt_right = (*thisNode)->cnt_left;\n            (*thisNode)->cnt_left += this->cnt_val + this->cnt_left;\n        }\n    }\n    int larger(T v) {\n        if (v == val)\n            return cnt_right;\n        if (v < val) {\n            return cnt_val + cnt_right + (left == nullptr ? 0 : left->larger(v));\n        }\n        return right == nullptr ? 0 : right->larger(v);\n    }    \n};\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> a1{nums[0]}, a2{nums[1]};\n        auto r1 = new TreeNodeWithCounter(nums[0]), r2 = new TreeNodeWithCounter(nums[1]);\n        for (int i = 2; i < nums.size(); ++i) {\n            int l1 = r1->larger(nums[i]), l2 = r2->larger(nums[i]);\n            if (l1 < l2 || (l1 == l2 && a2.size() < a1.size())) {\n                a2.push_back(nums[i]);\n                r2->insert(nums[i], &r2);\n            }            \n            else {\n                a1.push_back(nums[i]);\n                r1->insert(nums[i], &r1); \n            }\n        }\n        delete r1, r2;\n        a1.insert(end(a1), begin(a2), end(a2));\n        return a1;\n    }  \n};\n```\n
['C']