Method mergeSort

493. Reverse Pairs/Solution.cpp:18–43

    Solution():rev_pair(0) {}

    void mergeSort(int l, int r) {
        if (l + 1 >= r) return;     // zero or one element
        int m = (l + r) >> 1;       // two element : m = l + 1
        mergeSort(l, m);
        mergeSort(m, r);
        int i = 0, j = 0;
        while (j + m < r and i + l < m) {
            if (n[i + l] > 2L * n[j + m]) {
                rev_pair += m - l - i;
                j ++ ;
            } else {
                i ++ ;
            }
        }
        // merge
        vector<int> buf;
        buf.reserve(r - l);
        for (i = j = 0; i + l < m and j + m < r;) {
            if (n[i + l] > n[j + m]) buf.push_back(n[j++ + m]);
            else buf.push_back(n[i++ + l]);
        }
        while (i + l < m) buf.push_back(n[i++ + l]);
        while (j + m < r) buf.push_back(n[j++ + m]);
        for (int i = 0; i < buf.size(); i++)
            n[i + l] = buf[i];
    }

    int reversePairs(vector<int>& nums) {
        if (nums.size() <= 1) return 0;