https://leetcode.com/problems/reverse-pairs/#/description
和315, 327是一类题。
分治法，合并的过程就是归并排序，在归并的过程中，对右半边，统计满足nums[j] < nums[i] / 2的元素的个数即可。
class Solution { public:int reversePairs(vector<int>& nums) {if (nums.empty()) return 0;return count(nums, 0, nums.size() - 1);} private:int count(vector<int>& nums, int start, int end) {if (start >= end) return 0;int mid = start + (end - start) / 2;int left = count(nums, start, mid);int right = count(nums, mid+1, end);int cross = merge(nums, start, mid ,end);return ( left + right + cross );}int merge(vector<int>& nums, int start, int mid, int end) {int cnt = 0, p = start, q = mid + 1, r = 0;vector<int> helper(end-start+1);// 统计vector<int>::iterator up, low = nums.begin() + mid+1;for (int i = start; i <= mid; ++i) {up = std::upper_bound(nums.begin() + mid+1, nums.begin() + end+1, ceil(nums[i] / 2.0)-1); // 不包含nums[i]/2cnt += (up - low);}// 归并while (p <= mid && q <= end) {if (nums[p] < nums[q]) helper[r++] = nums[p++];else helper[r++] = nums[q++];}while (p <= mid) helper[r++] = nums[p++];while (q <= end) helper[r++] = nums[q++];copy(helper.begin(), helper.end(), nums.begin() + start);return cnt;} }; leetcode 327，是对前缀和数组的操作（涉及到区间统计，思维惯性是往前缀和或者区间DP方向走），若设S(i)表示nums[0..i]之和，S(i,j)表示nums[i...j]之和，计数条件就是lower <= S(i,j) <= upper，即lower <= S(j) - S(i-1) <= upper，即S(i-1)+lower <= S(j) <= S(i-1) + upper；逆序对以及今天的问题，都是对原数组操作，只是条件变为了nums(i) > 2*nums(j)，或nums(j) < nums(i) / 2，按不等式条件进行统计即可，其他形式的统计亦然。
注意，虽然字面意思是归并排序，但是因果关系并不是“归并排序有统计的功能”，而是为了加速计数过程，最好能创造一些条件，比如“数组能有序，而且不改变结果”。如果说解决这个问题的出发点是分治，只不过恰好统计的过程需要做排序，而这样的实现碰巧就是归并排序~