一道归并排序求逆序对的变体题。需要注意的是输入数据乘以2后可能超出int范围。

　　AC代码如下：

1 class Solution { 2     vector
      
        merge(vector
       
         a1, vector
        
          a2, int& sum) 3     { 4         vector
         
           merged; 5         int p1 = 0, p2 = 0; 6         for (int i = 0,j=0; i
          
           2*(long long)a2[j];j++); 9             sum+=j;10         }11         while (p1 != a1.size() && p2 != a2.size())12         {13             if (a1[p1]>a2[p2])14             {15                 merged.push_back(a2[p2]);16                 p2++;17             }18             else19             {20                 merged.push_back(a1[p1]);21                 p1++;22             }23         }24         while (p1 != a1.size())25         {26             merged.push_back(a1[p1]);27             p1++;28         }29         while (p2 != a2.size())30         {31             merged.push_back(a2[p2]);32             p2++;33         }34         return merged;35     }36 37     int mergeSort(vector
           
            & nums, int l, int r)38 {39 int sum = 0;40 if (l + 1 >= r)41 {42 return 0;43 }44 else45 {46 int m = (l + r) / 2;47 sum += mergeSort(nums, l, m);48 sum += mergeSort(nums, m, r);49 vector
            
              vl, vr, merged;50 for (int i = l; i
             

& nums) {69 return mergeSort(nums, 0, nums.size());70 }71 };