题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。  即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的数字数据范围：    对于%50的数据,size<=10^4    对于%75的数据,size<=10^5    对于%100的数据,size<=2*10^5示例1输入1,2,3,4,5,6,7,0输出7

 

思路：

 

                                                     

 

     

       过程：p1大于p2，因为这时左右两边都是排序数组，所以逆序对是{7,6},{7,4}，数目等于此时p2结束位置的右边数组元素个数，p2-p1，

然后按照归并的过程，--p1，记住这个稍微改动的就是归并排序以前是从开始位置比较，这里是从最后一个位置开始比较，采用--的形式，之后需要排序才能copy会原数组，而且这道题不能采用以前的mergesort，就是tmp{vec}，这种，必须采用

vector
      
        tempvec;for (int iz = lo; iz <= hi; ++iz) {      vec[iz] = tempvec[iz - lo];}
      

才不超时。

 

class Solution {public:    long long mergesort(vector
      
        &data,int start,int mid,int end){        int lpos = mid,rpos = end;        vector
       
         tmp;                // vector
        
          tmp{data}超时原因应该是copy占时间        long long cnt = 0;        while(lpos >= start && rpos >= mid + 1){            if(data[lpos] > data[rpos]){                cnt += rpos - mid;                tmp.push_back(data[lpos--]);            }            else{                 tmp.push_back(data[rpos--]);            }                    }        while(lpos >= start ){             tmp.push_back(data[lpos--]);                   }        while(rpos >= mid + 1){             tmp.push_back(data[rpos--]);          }        sort(tmp.begin(),tmp.end());        for (int i = start; i <= end; ++i) {                data[i] = tmp[i - start];        }        return cnt;    }           long long merge(vector
         
           &data,int start,int end){        if(start >= end){            return 0;        }        long long res = 0;        int  mid = start + (end - start) / 2;        res += merge(data,start,mid);        res += merge(data,mid + 1,end);        res += mergesort(data,start,mid,end);        return res;            }    int InversePairs(vector
          
            data) {        if(data.size() <= 1){            return 0;        }        long long cnt = 0;        cnt = merge(data,0,data.size() - 1);        return cnt % 1000000007;    }};