315.计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：

输入：nums = [-1]
输出：[0]
示例 3：

输入：nums = [-1,-1]
输出：[0,0]

思路:归并排序

数组中的元素进行归并排序时，在merge阶段，即对两个有序数组的合并过程中，每当执行 nums[i] = tmp[left] 时，就可以确定 tmp[left] 这个元素后面比它小的元素个数为 j - (mid+1)。 

举个栗子：

nums = [5,2,6,1] 

归并排序树 ：

                  1 2 5 6

                /             \

            2  5            1  6

          /       \          /      \

       5          2      6         1

采用归并排序（后序遍历），自底向上遍历

1。单个结点5；

2。单个结点2；

3。5、2这两个有序数组合并。[5,2]，low=0,mid=0,high=1，取nums[i]=temp[right]，此时不需要更新count，right++后right==high+1，nums[i]=temp[left]，此时需要更新count，count[nums[i].second]=right-(mid+1)=1；                                        counts[1,0,0,0]

4。单个结点6；

5。单个结点1；

6。6、1这两个有序数组合并，情况同3；                                    counts[1,0,1,0]

7。2，5、1，6这两个有序数组合并。[2,5,1,6],low=0,mid=1,high=3,取nums[i]=temp[right]，right

++，不需要更新count；之后取nums[i]=temp[left]，left++,此时需要更新count，count=1，counts[1,1,1,0];再之后nums[i]=temp[left]，继续更新count，count=1, counts[2,1,1,0]

实际上，就是根据归并排序时，自底向上的顺序，分解子问题。在 merge阶段，当nums[lo..mid]和nums[mid+1..hi] 两个子数组完成排序后，对于 nums[lo..mid] 中的每个元素 nums[i]，去 nums[mid+1..hi] 中寻找符合条件的 nums[j] 。例如5右侧小于它的元素的个数，就是[5,2]中5右侧小于它的元素个数1，再加上[2,5,1,6]中5右侧小于它的元素个数1，两数相加，得到count=2。

class Solution {
public:
    vectorint,int>> arr;   
    vector<int> counts; 
    vectorint,int>> tmp;
    vector<int> countSmaller(vector<int>& nums) 
    {
        counts.resize(nums.size());
        tmp.resize(nums.size());
        arr.resize(nums.size());
        for(int i=0;isize();i++)
        {
            arr[i]=make_pair(nums[i],i);
        }
        sort(arr,0,nums.size()-1);
        return counts;
    }
    void sort(vectorint,int>>&arr,int low,int high)
    {
        if(low>=high)
        return ;
        int mid=low+(high-low)/2;
        sort(arr,low,mid);
        sort(arr,mid+1,high);
        merge(arr,low,mid,high);
    }
    void merge(vectorint,int>>& arr,int low,int mid,int high)
    {
        for(int i=low;i<=high;i++)
        {
            tmp[i]=arr[i];
        }
        int left=low;
        int right=mid+1;
        for(int i=low;i<=high;i++)
        {
            if(left==mid+1)
            {
                arr[i]=tmp[right];
                right++;
            }
            else if(right==high+1)
            {
                arr[i]=tmp[left];
                left++;
                counts[arr[i].second]+=right-(mid+1);
            }
            else if(tmp[left]
            {
                arr[i]=tmp[left];
                left++;
                counts[arr[i].second]+=right-(mid+1);
            }
            else
            {
                arr[i]=tmp[right];
                right++;
            }
        }
    }
 
};