// see more at https://www.youtube.com/watch?v=j68OXAMlTM4
// https://leetcode.com/problems/reverse-pairs/discuss/97268/general-principles-behind-problems-similar-to-reverse-pairs
// http://www.cnblogs.com/grandyang/p/6657956.htmlclass Solution {
public:
int reversePairs(vector<int>& nums) {
return reversePairs(nums, , nums.size()-);
}
int reversePairs(vector<int>& nums, int begin, int end) {
if (begin >= end) return ;
int m = begin + (end - begin) / ;
int res = reversePairs(nums, begin, m);
res += reversePairs(nums, m+, end); int *p = new int[end-begin+]; int i = begin, j = m+;
while (i <= m && j <= end) {
if (nums[i] > 2L * nums[j]) { // avoid overflow
res += m - i + ;
j++;
}
else {
i++;
}
} i = begin; j = m+; int k = ;
while (i <= m && j <= end) {
if (nums[i] > nums[j])
p[k++] = nums[j++];
else
p[k++] = nums[i++];
}
while (i <= m)
p[k++] = nums[i++];
while (j <= end)
p[k++] = nums[j++];
for (int i = begin; i <= end; i++) {
nums[i] = p[i-begin];
}
//sort(nums.begin() + begin, nums.begin() + end+1); return res;
}
};