315. Count of Smaller Numbers After Self(方法二：使用MergeSort)

使用树状数组求解：http://maybi.cn/wp_siukwan/?p=850

1.这道题目跟求逆序对的题目类似，但是求逆序对的题目只需要求出总的逆序对数量即可，而这道题目要求求出每个数的右边比它小的数的个数。

2.按照逆序对的思想去编写的时候会发现，mergeSort中会有一个交换赋值的过程，导致我们不能简单的使用用一个数组根据下标去记录当前数的右边比它小的数的个数，因为这个数排序后，不在原下标位置。

3.所以需要设计一个数据结构，这个数据结构记录了原始数组的val，原始数组的idx，以及所求值cnt，然后对这个新的数据结构数组进行mergeSort，同时进行统计。除去复制和复制的O(n)时间复杂度，剩下的就是MergeSort的时间复杂度O(nlogn)，所以时间复杂度为O(nlogn)，空间复杂度为O(n)。

AC代码：

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<node> num(nums.size());
        for(int i=0;i<nums.size();++i)
        {
            num[i].idx=i;
            num[i].cnt=0;
            num[i].val=nums[i];
        }
        vector<node> tmpNums(nums.size());
        
        Msort(num,tmpNums,0,num.size()-1);
        
        vector<int> result(nums.size());
        for(int i=0;i<num.size();++i)
        {
            result[num[i].idx]=num[i].cnt;
        }
        
        return result;
    }
    struct node{
        int val;//值
        int cnt;//右边比它大的数
        int idx;//原来的idx
        node():val(0),cnt(0),idx(0){};
    };
    void Merge(vector<node>&nums,vector<node>&tmpNums,int l,int k,int r)
    {
        int i=l,j=k+1;
        int idx=l;
        while(i<=k&j<=r)
        {
            if(nums[i].val<=nums[j].val)
            {//填充左边的数，证明之前填充的右边的数比这个数小，我们需要查询之前右边填充了多少个数字
                nums[i].cnt+=j-(k+1);
                tmpNums[idx++]=nums[i++];
            }
            else
                tmpNums[idx++]=nums[j++];
        }
        while(i<=k)
        {
            nums[i].cnt+=j-(k+1);
            tmpNums[idx++]=nums[i++];
        }
        while(j<=r)
            tmpNums[idx++]=nums[j++];
        
        for(i=l;i<=r;++i)
        {
            nums[i]=tmpNums[i];
        }
    }
    
    void Msort(vector<node>&nums,vector<node>&tmpNums,int l,int r)
    {
        if(l>=r) return ;
        
        int k=(l+r)/2;
        Msort(nums,tmpNums,l,k);
        Msort(nums,tmpNums,k+1,r);
        Merge(nums,tmpNums,l,k,r);
    }
};