1 class Solution {
 2 public:
 3     int reversePairs(vector<int>& nums) {
 4         vector<int> tmp(nums.size());
 5         return mergeSort(nums, tmp, 0, nums.size()-1);
 6     }
 7 
 8     int mergeSort(vector<int> &nums, vector<int>& tmp, int L, int R) {
 9         if(L >= R) {
10             return 0;
11         }
12 
13         int reversePairsNum = 0;
14         int mid = (L + R) / 2;
15         reversePairsNum = mergeSort(nums, tmp, L, mid) + mergeSort(nums, tmp, mid+1, R);
16 
17         int k = 0;
18         int i = L, j = mid+1;
19         while(i <= mid && j <= R) {
20             if(nums[i] <= nums[j]) {
21                 tmp[k++] = nums[i++];
22                 reversePairsNum += j-1-mid; //第i个元素和区间[mid+1, j-1]中的每个元素组成一个逆序对
23             } else {
24                 tmp[k++] = nums[j++];
25             }
26         }
27 
28         while(i <= mid) {
29             tmp[k++] = nums[i++];
30             reversePairsNum += j-1-mid; //注意：执行此循环的时候说明j已经等于R+1了
31         }
32 
33         while(j <= R) {
34             tmp[k++] = nums[j++];   //注意：执行此循环的时候说明i已经等于mid+1了
35         }
36 
37         copy(tmp.begin(), tmp.begin()+k, nums.begin()+L);
38 
39         return reversePairsNum;
40     }
41 };