AcWing 65.数组中的逆序对（困难）

题目描述

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。

样例
输入：[1,2,3,4,5,6,0]
输出：6

参考：https://www.bilibili.com/video/BV1Hv41167ft?from=search&seid=2747792850762973218

归并排序的典型应用
思路： 如果是从小到大的有序数组，是不存在逆序对的，产生逆序对的一定是无序或者递减的
无序变有序的过程就是将逆序对的两个元素进行交换，从而消灭逆序对
所以把交换的次数数出来，就是逆序对的个数
最简单的是冒泡（冒泡排序会进行逆序对的交换），但是时间复杂度高
用归并来实现排序。

在基础归并上加了一个句30行的：count+=(mid-i+1)
也就是左边子列的i大于右边子列j时候，由于左边是递增排序的，说明左边i之后的数字都大于j
所以逆序对就是左边子列i之后的元素的个数，就是mid-i+1

class Solution {
public:
    void merge(vector<int>& nums,int left,int right){
        if(left>=right) return;
        int mid=left+(right-left)/2;
        merge(nums,left,mid);
        merge(nums,mid+1,right);
        sort2vector(nums,left,mid,right);
        //left是左边子列开头，mid是左边子列结尾；mid+1是右边子列开头，right是右边子列结尾
    }
    void sort2vector(vector<int>& nums,int left,int mid,int right){

        int i=left,j=mid+1;
        int len=right-left+1;
        while(i<=mid&&j<=right){    
            if(nums[i]<=nums[j]) 
                ans.push_back(nums[i++]);
            else{
                count+=(mid-i+1);//对于[5 7] [4 6] 5>4，所以左边都大于4，count+2；
                ans.push_back(nums[j++]);
            } 
        }
        while(i<=mid)  ans.push_back(nums[i++]);
        while(j<=right)  ans.push_back(nums[j++]);
        for(int i=0;i<len;i++)
            nums[i+left]=ans[i];//ans是从0开始，但是nums从left开始
        ans.clear();
    }
    int reversePairs(vector<int>& nums) {
        merge(nums,0,nums.size()-1);
        return count;
    }
private:
    int count=0;
    vector<int> ans;  //把暂存的vector定义外面，每次用完clear，用时会少
};