Reverse Pairs

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> buf(nums.size());
        return mergeSort(nums, buf, 0, (int)nums.size() - 1);
    }
private:
    int mergeSort(vector<int>& a, vector<int>& buf, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + (hi - lo) / 2;
        int count = mergeSort(a, buf, lo, mid) + mergeSort(a, buf, mid + 1, hi);
        int j = mid + 1;
        for (int i = lo; i <= mid; ++i) {
            while (j <= hi && (long long)a[i] > 2LL * a[j]) ++j;
            count += j - (mid + 1);
        }
        // merge
        int p = lo, q = mid + 1, k = lo;
        while (p <= mid && q <= hi) buf[k++] = (a[p] <= a[q] ? a[p++] : a[q++]);
        while (p <= mid) buf[k++] = a[p++];
        while (q <= hi) buf[k++] = a[q++];
        for (int t = lo; t <= hi; ++t) a[t] = buf[t];
        return count;
    }
};

func reversePairs(nums []int) int {
    buf := make([]int, len(nums))
    var ms func(lo, hi int) int
    ms = func(lo, hi int) int {
        if lo >= hi {
            return 0
        }
        mid := lo + (hi-lo)/2
        count := ms(lo, mid) + ms(mid+1, hi)
        j := mid + 1
        for i := lo; i <= mid; i++ {
            for j <= hi && int64(nums[i]) > 2*int64(nums[j]) {
                j++
            }
            count += j - (mid + 1)
        }
        p, q, k := lo, mid+1, lo
        for p <= mid && q <= hi {
            if nums[p] <= nums[q] {
                buf[k] = nums[p]
                p++
            } else {
                buf[k] = nums[q]
                q++
            }
            k++
        }
        for p <= mid {
            buf[k] = nums[p]
            p++
            k++
        }
        for q <= hi {
            buf[k] = nums[q]
            q++
            k++
        }
        for t := lo; t <= hi; t++ {
            nums[t] = buf[t]
        }
        return count
    }
    return ms(0, len(nums)-1)
}

from typing import List

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        buf = [0] * len(nums)

        def merge_sort(lo: int, hi: int) -> int:
            if lo >= hi:
                return 0
            mid = lo + (hi - lo) // 2
            count = merge_sort(lo, mid) + merge_sort(mid + 1, hi)
            j = mid + 1
            for i in range(lo, mid + 1):
                while j <= hi and nums[i] > 2 * nums[j]:
                    j += 1
                count += j - (mid + 1)
            p, q, k = lo, mid + 1, lo
            while p <= mid and q <= hi:
                if nums[p] <= nums[q]:
                    buf[k] = nums[p]
                    p += 1
                else:
                    buf[k] = nums[q]
                    q += 1
                k += 1
            while p <= mid:
                buf[k] = nums[p]
                p += 1
                k += 1
            while q <= hi:
                buf[k] = nums[q]
                q += 1
                k += 1
            for t in range(lo, hi + 1):
                nums[t] = buf[t]
            return count

        return merge_sort(0, len(nums) - 1)

function reversePairs(nums) {
    const buf = new Array(nums.length);
    const mergeSort = (lo, hi) => {
        if (lo >= hi) return 0;
        const mid = lo + Math.floor((hi - lo) / 2);
        let count = mergeSort(lo, mid) + mergeSort(mid + 1, hi);
        let j = mid + 1;
        for (let i = lo; i <= mid; i++) {
            while (j <= hi && nums[i] > 2 * nums[j]) j++;
            count += j - (mid + 1);
        }
        let p = lo, q = mid + 1, k = lo;
        while (p <= mid && q <= hi) {
            buf[k++] = nums[p] <= nums[q] ? nums[p++] : nums[q++];
        }
        while (p <= mid) buf[k++] = nums[p++];
        while (q <= hi) buf[k++] = nums[q++];
        for (let t = lo; t <= hi; t++) nums[t] = buf[t];
        return count;
    };
    return mergeSort(0, nums.length - 1);
}

class Solution {
    private int[] buf;
    private int[] a;

    public int reversePairs(int[] nums) {
        a = nums;
        buf = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }

    private int mergeSort(int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + (hi - lo) / 2;
        int count = mergeSort(lo, mid) + mergeSort(mid + 1, hi);
        int j = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j <= hi && (long) a[i] > 2L * a[j]) j++;
            count += j - (mid + 1);
        }
        int p = lo, q = mid + 1, k = lo;
        while (p <= mid && q <= hi) buf[k++] = (a[p] <= a[q] ? a[p++] : a[q++]);
        while (p <= mid) buf[k++] = a[p++];
        while (q <= hi) buf[k++] = a[q++];
        for (int t = lo; t <= hi; t++) a[t] = buf[t];
        return count;
    }
}

function reversePairs(nums: number[]): number {
    const buf: number[] = new Array(nums.length);
    const mergeSort = (lo: number, hi: number): number => {
        if (lo >= hi) return 0;
        const mid = lo + Math.floor((hi - lo) / 2);
        let count = mergeSort(lo, mid) + mergeSort(mid + 1, hi);
        let j = mid + 1;
        for (let i = lo; i <= mid; i++) {
            while (j <= hi && nums[i] > 2 * nums[j]) j++;
            count += j - (mid + 1);
        }
        let p = lo, q = mid + 1, k = lo;
        while (p <= mid && q <= hi) {
            buf[k++] = nums[p] <= nums[q] ? nums[p++] : nums[q++];
        }
        while (p <= mid) buf[k++] = nums[p++];
        while (q <= hi) buf[k++] = nums[q++];
        for (let t = lo; t <= hi; t++) nums[t] = buf[t];
        return count;
    };
    return mergeSort(0, nums.length - 1);
}