1. 二叉查找树版

function InversePairs(data) {
    if (data.length < 2) return 0;
    let mod = 1000000007;
    var ret = 0;
    function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null
        this.lkids = 0;
        this.rkids = 0;
    }
    function Insert(p, x) {
        let n = 0;
        while (true) {
            if (x > p.val) {
                p.rkids++;
                if (p.right) p = p.right;
                else {
                    p.right = new TreeNode(x);
                    break;
                }
            } else {
                p.lkids++;
                n += p.rkids + 1;
                if (p.left) p = p.left;
                else {
                    p.left = new TreeNode(x);
                    break;
                }
            }
        }
        ret += n;
        if (ret >= mod) ret -= mod;
    }

    let r = new TreeNode(data[0]);
    for (let i = 1; i < data.length; i++) {
        Insert(r, data[i]);
    }
    return ret;
}  

	2. 树状数组版

function InversePairs(data) {
    if (data.length < 2) return 0;
    var ret = 0;
    let mod = 1000000007;
    let bit = new Array(2000002).fill(0); 

    function add(i, d) {
        while (i < bit.length) {
            bit[i] += d;
            i += i & -i;
        }
    }

    function sum(x) {
        let sum = 0;
        while (x > 0) {
            sum += bit[x];
            x -= x & -x;
        }
        return sum;
    }

    for (let i = 0; i < data.length; i++) {
        ret += i - sum(data[i] + 1);
        add(data[i] + 1, 1);
    }

    return ret % mod;
}

	

/* 这个超时了，我也不知道是为什么,思路是一样的，都是分治的思想
function InversePairs(data) {
  // write code here
  /**
   * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总
   * 数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
   *
   * 借用分治的的思想，先两两等分，对每一份统计逆序对的数量，并进行排序，排序之后进行合并，边合并边统计逆序对的数量

  if (!data || data.length < 2) {
    return 0
  }
  let count = 0
  const mergeArr = (arr, first, mid, end) => {
    //传入的mid是取不到的，前半段为first~mid-1，后半段为mid~end-1
    // 将数组的一段进行合并排序
    let temp = []   // 临时数组，用于保存end-first排序之后的序列
    let i = 1, j = 1
    while (i <= mid - first && j <= end - mid) {
      if (arr[mid - i] > arr[end - j]) {
        temp.unshift(arr[mid - i])
        count += (end - j - mid + 1)
        i++
      } else {
        //此时说明前面的数小于后面的数，未形成逆序对
        temp.unshift(arr[end - j])
        j++
      }
    }

    while (i <= mid - first) {
      temp.unshift(arr[mid - i])
      i++
    }

    while (j <= end - mid) {
      temp.unshift(arr[end - j])
      j++
    }
    //console.log(temp)
    arr.splice(first, end - first, ...temp)
  }

  function mergeSort(arr, first, end) {
    //递归进行归并排序
    let mid = (first + end) >> 1
    if (first < mid) {
      mergeSort(arr, first, mid)
      mergeSort(arr, mid, end)
      mergeArr(arr, first, mid, end)
      //console.log(arr)
    }
  }

  mergeSort(data, 0, data.length)
  //console.log(count)
  return count % 1000000007
}

//InversePairs([2,5,1,4,6,8,3,7])
module.exports = {
    InversePairs : InversePairs
};
*/
    
function InversePairs(data)
{
    var copy = data.slice();
    return mergeInversePairs(data, copy, 0, data.length - 1) % 1000000007;
}
function mergeInversePairs(arr, copy, begin, end) {
    if(begin === end) {
        return 0;
    }
    var mid = begin + end >> 1;
    var left = mergeInversePairs(arr, copy, begin, mid);
    var right = mergeInversePairs(arr, copy, mid + 1, end);
    var num = 0, i = mid, j = end, k = end;
    while(i >= begin && j >= mid + 1) {
        if(arr[i] <= arr[j]) {
            copy[k--] = arr[j--];
        } else {
            num += j - mid;
            copy[k--] = arr[i--];
        }
    }
    while(i >= begin) copy[k--] = arr[i--];
    while(j >= mid + 1) copy[k--] = arr[j--];
    for(var s = begin; s <= end; s++)
    {
        arr[s] = copy[s];
    }
    return num + left + right;
}
module.exports = {
    InversePairs : InversePairs
};

function InversePairs(data)
{
    if(!data||data.length<2) return 0;
    let copy=data.slice(),count=0;
    count=mergeCount(data,copy,0,data.length-1);
    return count%1000000007;
}
function mergeCount(data,copy,start,end){
    if(start==end) return 0;
    let mid=(end-start)>>1,
        left=mergeCount(copy,data,start,start+mid),//注意参数，copy作为data传入
        right=mergeCount(copy,data,start+mid+1,end),//注意参数，copy作为data传入         [p,q,count,copyIndex]=[start+mid,end,0,end];
    while(p>=start&&q>=start+mid+1){
        if(data[p]>data[q]){
            copy[copyIndex--]=data[p--];
            count=count+q-start-mid;
        }else{
            copy[copyIndex--]=data[q--];
        }
    }
    while(p>=start){
        copy[copyIndex--]=data[p--];
    }
    while(q>=start+mid+1){
        copy[copyIndex--]=data[q--];
    }
    return count+left+right;
}

function InversePairs(data) {
    // write code here
    var sortedArray = getSorted(data);
    return sortedArray.count;
}

function getSorted(data) {
    var length = data.length;
    if (length <= 1) return data;
    var mid = Math.floor(length / 2),
        left = data.slice(0, mid),
        right = data.slice(mid, length);
    return merge(getSorted(left), getSorted(right));
}

function merge(left, right) {
    var li = left.length - 1,
        ri = right.length - 1;
    var ansArray = [];
    var count = (left.count ? left.count : 0) + (right.count ? right.count : 0);
    for (; li >= 0 && ri >= 0;) {
        if (left[li] > right[ri]) {
            count += ri + 1;
            if (count > 1000000007) count = count % 1000000007;
            ansArray.unshift(left[li]);
            li--;
        } else {
            ansArray.unshift(right[ri]);
            ri--;
        }
    }
    while (li >= 0) {
        ansArray.unshift(left[li--]);
    }
    while (ri >= 0) {
        ansArray.unshift(right[ri--]);
    }
    ansArray['count'] = count % 1000000007;
    return ansArray;
}
//超时............