C++ O(NlogN) Mergesort
Solution\n\ndraw lessons from Leetcode315 Count of Smaller Numbers After Self\uFF0C we can using Mergesort\nt0 means the number of Smaller Numbers After Self\nt
### Solution\n\ndraw lessons from Leetcode315 Count of Smaller Numbers After Self\uFF0C we can using Mergesort\nt0 means the number of Smaller Numbers After Self\nt1 means the number of Bigger Numbers After Self\n\n### Code\n\n```cpp\nclass SolutionOfLeetCode315 {\npublic:\n    using pii = pair<int, int>;\n    vector<vector<int>> countSmaller(vector<int>& nums) {\n        int n = nums.size();\n        vector<pii> v(n);\n        vector<vector<int>> res(2, vector<int>(n, 0));\n        for (int i = 0; i < n; i++)  v[i] = {nums[i], i}; \n        merge_sort(v.begin(), v.end(), res, true); \n        for (int i = 0; i < n; i++)  v[i] = {nums[i], i}; \n        merge_sort(v.begin(), v.end(), res, false);\n        return res;\n    }\nprivate:\n    void merge_sort(vector<pii>::iterator l, vector<pii>::iterator r,\n                    vector<vector<int>> &res, bool IsGreater) {\n        if (l+1 < r) {\n            auto mid = l + (r-l)/2;\n            merge_sort(l, mid, res, IsGreater);\n            merge_sort(mid, r, res, IsGreater);\n            merge(l, r, res, IsGreater);\n        }  \n    }\n    \n    void merge(vector<pii>::iterator l, vector<pii>::iterator r, \n               vector<vector<int>> &res, bool IsGreater) {\n        int cnt = 0;\n        auto mid = l + (r-l)/2, p = l, q = mid;\n        while (p < mid || q < r) {\n            if (p < mid && q < r) {\n                if (q->first >= p->first) {\n                    if (!IsGreater) res[1][p->second] += r-q;\n                    IsGreater ? ++q : ++p;\n                }\n                else {\n                    if (IsGreater) res[0][p->second] += r-q;\n                    IsGreater ? ++p : ++q;\n                }\n            }\n            else if (p < mid) p++;\n            else q++;\n        }\n        if (IsGreater) inplace_merge(l, mid, r, std::greater<>());\n        else inplace_merge(l, mid, r, std::less<>());\n    }\n};\n\n\n\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        //preprocess\n        class SolutionOfLeetCode315 A;\n        auto temp = A.countSmaller(rating);\n        auto &t0  = temp[0], t1 = temp[1];\n        \n        int n = rating.size(), res = 0;\n        vector<int> sorted_rating(rating);\n        sort(sorted_rating.begin(), sorted_rating.end());\n        \n        for (int i = 1; i < n-1; ++i) {\n            int pos = lower_bound(sorted_rating.begin(), sorted_rating.end(), rating[i]) \n                      - sorted_rating.begin(); \n            res += t0[i]*(n-1-pos-t1[i]) + t1[i]*(pos-t0[i]);\n        }\n        return res;\n    }\n};\n\n\n```
[]