Inverse Pairs

来源：Meetqun, 一亩三分地，Google

原帖：http://www.fgdsb.com/2015/01/03/inverse-pairs/

题目：
Given an integer array, return the number of all inverse pairs. For example:
{7, 5, 6, 4}
There are five inverse pairs in total:
(7,6), (7,5), (7,4), (6,4), (5,4)
The result should be 5.

思路：
用BST, 线段树，或者merge sort. 从后向前merge然后计算pair number.

代码：

 int mergeSort(vector<int>& num, int s, int e, vector<int>& dup) {   
     if (s >= e) return 0;   
     int mid = s + (e - s) / 2;   
     int l = mergeSort(num, s, mid, dup);   
     int r = mergeSort(num, mid+1, e, dup);   
     //cout << "start: " << s << " end " << e << " mid " << mid;   
     //cout << " l " << l << " r " << r << endl;   
   
     int sum = l + r;   
     for (int i = s; i <= e; ++i) {   
         dup[i] = num[i];   
     }   
     int cur = e, i = mid, j = e; // back -> front   
     while (i >= s && j > mid) {   
         if (dup[i] <= dup[j]) {   
             num[cur--] = dup[j--];   
         } else if (dup[i] > dup[j]) {   
             num[cur--] = dup[i--];   
             sum += j - mid;   
         }   
     }   
     while (i >= s) {   
         num[cur--] = dup[i--];   
     }   
     while (j > mid) {   
         num[cur--] = dup[j--];   
     }   
     return sum;   
 }   
   
 int inverse(vector<int>& num) {   
     if (num.empty() || num.size() == 1) return 0;   
     vector<int> dup(num);   
     return mergeSort(num, 0, num.size()-1, dup);   
 }   
   
 int main() {   
     vector<int> num = {7, 5, 6, 4};   
     cout << inverse(num) << endl;   
     return 0;   
 }