Divide and Conquer 分治法

// Median of Two Sorted Arrays
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size();
        const int m = nums2.size();
        if ((n + m) % 2 != 0)
            return find_kth(nums1.begin(), n, nums2.begin(), m, (n + m + 1) / 2);
        else
            return (find_kth(nums1.begin(), n, nums2.begin(), m, (n + m) / 2) + find_kth(nums1.begin(), n, nums2.begin(), m, (n + m) / 2 + 1)) / 2.0;
    }
    
    int find_kth(vector<int>::const_iterator iter1, int n, vector<int>::const_iterator iter2, int m, int k) {
        if (n > m)
            return find_kth(iter2, m, iter1, n, k);
        if (n == 0)
            return *(iter2 + k - 1);
        if (k == 1)
            return min(*iter1, *iter2);
        int ia = min(k / 2, n), ib = k - ia;
        if (*(iter1 + ia - 1) == *(iter2 + ib - 1)) {
            return *(iter1 + ia - 1);
        } else if (*(iter1 + ia - 1) < *(iter2 + ib - 1)) {
            return find_kth(iter1 + ia, n - ia, iter2, m, k - ia);
        } else {
            return find_kth(iter1, n, iter2 + ib, m - ib, k - ib);
        }
    }
};

// Reverse Pairs
// Method: Enhance Merge Sort
// Time Complexity: O(nlogn)
// Algorithmic Paradigm: Divide and Conquer
class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& nums2, int left, int right) {
        int count = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            int count1 = mergeSort(nums, nums2, left, mid);
            int count2 = mergeSort(nums, nums2, mid + 1, right);
            int count3 = 0;

            if (right == left + 1) {
                // 这个if可以省略
                if (nums[left] > 2 * (double)nums[right])
                    count3 = 1;
                if (nums[right] < nums[left])
                    swap(nums[left], nums[right]);
            } else {
                for (int i = left, j = mid + 1; j <= right; j++) {
                    while (nums[i] <= 2 * (double)nums[j] && i <= mid)
                        i++;
                    if (i == mid + 1)
                        break;
                    count3 += (mid - i + 1);
                }

                int i = left, j = mid + 1, k = left;
                while (i <= mid && j <= right) {
                    if (nums[i] < nums[j])
                        nums2[k++] = nums[i++];
                    else
                        nums2[k++] = nums[j++];
                }
                while (i <= mid) {
                    nums2[k++] = nums[i++];
                }
                while (j <= right) {
                    nums2[k++] = nums[j++];
                }
                for (i = left; i <= right; i++)
                    nums[i] = nums2[i];
            }

            count = count1 + count2 + count3;
        }
        return count;
    }

    int reversePairs(vector<int>& nums) {
        vector<int> nums2(nums.size());
        return mergeSort(nums, nums2, 0, nums.size() - 1);
    }
};

// Count of Smaller Numbers After Self
// The smaller numbers on the right of a number are exactly #jumps from its right to its left during a stable sort. 
// Merge sort with added tracking of those right-to-left jumps
// http://www.geeksforgeeks.org/counting-inversions/
// two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        const int n = nums.size();
        vector<int> indices(n), results(n);
        for (int i = 0; i < n; i++)
            indices[i] = i;
        mergeSort(nums, indices, results, 0, n - 1);
        return results;
    }    
    void mergeSort(vector<int>& nums, vector<int>& indices, vector<int>& results, int low, int high) {
        if (low >= high)
            return;
        int mid = (low + high) / 2;
        mergeSort(nums, indices, results, low, mid);
        mergeSort(nums, indices, results, mid + 1, high);
        vector<int> sorted(high - low + 1), new_indices(high - low + 1);
        int i = low, j = mid + 1, k = 0, inversions = 0;
        while (i <= mid) {
            if (j > high || nums[i] <= nums[j]) {
                sorted[k] = nums[i];
                results[indices[i]] += inversions;
                new_indices[k++] = indices[i++];              
            } else {
                sorted[k] = nums[j];
                new_indices[k++] = indices[j++]; 
                inversions++;
            }
        }
        for (int i = 0; i < k; i++) {
            nums[low + i] = sorted[i];
            indices[low + i] = new_indices[i];
        }
    }
};

// Count of Range Sum
class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long long> sums(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++)
            sums[i + 1] = sums[i] + nums[i];
        return countRangeSum(sums, lower, upper, 0, sums.size() - 1);
    }
    int countRangeSum(vector<long long>& sums, int lower, int upper, int left, int right) {
        if (left >= right)
            return 0;
        // if (left + 1 == right) {
        //     int count = (sums[right] - sums[left] >= lower && sums[right] - sums[left] <= upper);
        //     if (sums[left] > sums[right])
        //         swap(sums[left], sums[right]); // Important!
        //     return count;
        // }
        int mid = (left + right) / 2;
        int count1 = countRangeSum(sums, lower, upper, left, mid);
        int count2 = countRangeSum(sums, lower, upper, mid + 1, right);
        int count3 = 0;
        // count[i] = count of a <= S[j] - S[i] <= b with j > i
        for (int i = left, j = mid + 1, k = mid + 1; i <= mid; i++) {            
            while (j <= right && sums[j] - sums[i] < lower)
                j++; // j is the first index satisfy sums[j] - sums[i] >= lower.
            while (k <= right && sums[k] - sums[i] <= upper)
                k++; // k is the first index satisfy sums[k] - sums[i] > upper
            if (j > right)
                break;
            count3 += (k - j); // Then the number of sums in [lower, upper] is k - j
        }        
        vector<int> sums_copy(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid) {
            if (j > right || sums[i] <= sums[j]) {
                sums_copy[k++] = sums[i++];
            } else {
                sums_copy[k++] = sums[j++];
            }
        }
        for (int i = 0; i < k; i++)
            sums[left + i] = sums_copy[i];
        return count1 + count2 + count3;
    }
};