数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：

对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

输入例子:

1,2,3,4,5,6,7,0

输出例子:

7

代码

int const MOD = 1000000007;
class Solution {
    vector<int> d;
    int P;
public:
    //利用归并排序求逆序对总数
    int InversePairs(vector<int> data) {
        this->d = data;
        this->P = 0;
        partition(0, this->d.size() - 1);
        return this->P;
    }
    
    void sum(int c) {
        this->P += c;
        if (this->P >= MOD) {
            this->P -= MOD;
        }
    }
    
    void partition(int s, int e) {
        if (s >= e) {
            return;
        }
        int m = (s + e) >> 1;
        partition(s, m);
        partition(m + 1, e);
        
        vector<int> st(e - s + 1, 0);
        
        int is = s, im = m + 1, k = s;
        while (k <= e) {
         	if (is > m) {//左边排完
               st[k - s] = this->d[im++];  
            } else if (im > e) {//右边排完
                st[k - s] = this->d[is++];
            } else {
                if (this->d[is] <= this->d[im]) {
                    st[k - s] = this->d[is++];
                } else {
                    st[k - s] = this->d[im++];  
                    sum(m - is + 1);
                }
                
            }
            ++k;
        }
        for (is = s, k = 0; is <= e; ++is, ++k) {
            this->d[is] = st[k]; 
        }
    }
    
};