描述：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。
思路：归并排序，在每次递归调用中，先对左半部分排序，然后统计右半部分每个值在左半部分的逆序对数
class Solution {
public:
/**
* @param A: an array
* @return: total of reverse pairs
*/
long long reversePairs(vector<int> &A) {
// write your code here
int ans = 0;
int len = A.size();
ans = DFS(A,0,A.size());
return ans;
}
int DFS(vector<int> &A,int left,int right)
{
if( right - left <= 1)
{
return 0;
}
int mid = (left + right) >> 1;
int res = DFS(A,left,mid) + DFS(A,mid,right);
sort(A.begin() + left,A.begin() + mid);
for( int i = mid;i < right; ++i )
{
res += A.begin() + mid - std::upper_bound(A.begin() + left,A.begin() + mid,A[i]);
}
return res;
}
