leettcode 剑指 Offer 51. 数组中的逆序对

 1 class Solution {
 2 public:
 3     int reversePairs(vector<int>& nums) {
 4         int n=nums.size();
 5         int a[n+1];
 6         function<int(int,int)>merge=[&](int l,int r)
 7         {
 8             if(l>=r)return 0;
 9             int mid=(l+r)>>1;
10             auto lcnt=merge(l,mid);
11             auto rcnt=merge(mid+1,r);
12             int p=l,pl=l,pr=mid+1,cnt=0;
13             while(pl<=mid&&pr<=r)
14             {
15                 if(nums[pr]<nums[pl])
16                 {
17                     cnt+=mid-pl+1;
18                     a[p++]=nums[pr++];
19                 }
20                 else a[p++]=nums[pl++];
21             }
22             while(pl<=mid)a[p++]=nums[pl++];
23             while(pr<=r)a[p++]=nums[pr++];
24             for(int i=l;i<=r;i++)nums[i]=a[i];
25             return cnt+lcnt+rcnt;
26         };
27         return merge(0,n-1);
28     }
29 };