数列A={a0,a1....an-1}中,如果一组数(ij)满足i>a且i<j,那么这组数就称为一个逆序,数列A中逆序的数量称为逆序数,逆序数与下述冒泡算法的交换次数****相等。

bubbleSort(A)
  cnt=0//逆序数
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] A[j-1]
        swap(A[j] A[j-1])
        cnt++
  return cnt

• 模板

#define oo (2147000000)
#define maxn (200000)

int L[maxn / 2 + 2], R[maxn / 2 + 2];

ll merge(int a[], int n, int left, int mid, int right) {
    int i, j, k;
    ll cnt = 0;
    int n1 = mid - left;
    int n2 = right - mid;
    for (i = 0; i < n1; i++) L[i] = a[left + i];
    for (i = 0; i < n2; i++) R[i] = a[mid + i];
    L[n1] = R[n2] = oo;
    i = j = 0;
    for (k = left; k < right; k++) {
        if (L[i] < R[j]) {
            a[k] = L[i++];
        } else {
            a[k] = R[j++];
            cnt += n1 - i; //=mid+j-k-1
        }
    }
    return cnt;
}

ll mergeSort(int a[], int n, int left, int right) {
    int mid;
    ll v1, v2, v3;
    if (left + 1 < right) {
        mid = (left + right) / 2;
        v1 = mergeSort(a, n, left, mid);
        v2 = mergeSort(a, n, mid, right);
        v3 = merge(a, n, left, mid, right);
        return v1 + v2 + v3;
    }
    return 0;
}

int main() {
    int a[maxn], n, i;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll ans = mergeSort(a, n, 0, n);
    cout << ans;
}