逆序对的两种算法【树状数组 / 归并排序】

• 对于数组A[1…n]，求逆序对对数。
• 可根据数据范围离散化。
• 以下算法时间复杂度：O（n * log n）。
• 逆序对对数最大为n*(n-1)/2，结果经常要用long long保存。

---

树状数组算法

1. 逐一读入a[i]。
2. 利用树状数组统计比a[i]小的数个数s，逆序对个数加上i - 1 - s。
3. 把a[i]计入树状数组，即结点i加1。
4. 代码：

#include<bits/stdc++.h>
 using namespace std;

 const int MN = 1005;//MN根据数据决定 
 int n, i, x, ans, c[MN];

 inline int lowbit(int x)
 {
    return x & (-x);
 }

 inline int sum(int x)
 {
    int s = 0;
    for(; x; x -= lowbit(x)) s += c[x];
    return s;
 }

 inline void add(int x)
 {
    for(; x < n; x += lowbit(x)) c[x] ++;
 }

 int main()
 {

    scanf("%d", &n);

    memset(c, 0, sizeof(c));
    for(i = 1, s = 0; i <= n; ++ i)
    {
        scanf("%d", &x);
        ans += i - 1 - sum(x);
        add(x);
    }

    printf("%d", ans);

    return 0;

 }

---

归并排序算法

1. 二分时，将数组a[l, r]分为a[l, mid]与a[mid + 1, r]（mid = (l + r) >> 1）分别归并排序。
2. 合并时，对于l <= i <= mid, mid + 1 <= j <= r，若a[i] > a[j]，则a[i, mid]都比a[j]大，逆序对对数加上mid - i + 1。
3. 代码：

#include<bits/stdc++.h>
 using namespace std;

 const int MN = 1005;//MN根据数据决定 
 int n, i, a[MN], b[MN], ans;

 inline void merge(int l, int r)
 {
    int mid = (l + r) >> 1, i, j, k;

    for(i = k = l, j = mid + 1; i <= mid && j <= r;)
    if (a[i] > a[j]) b[k ++] = a[j ++], ans += mid - i + 1;
    else b[k ++] = a[i ++];
    for(; i <= mid; i ++) b[k ++] = a[i];
    for(; j <= r; j ++) b[k ++] = a[j];

    for(i = l; i <= r; i ++) a[i] = b[i];
 }

 inline void merge_sort(int l, int r)
 {
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r);
 }

 int main()
 {

    scanf("%d", &n);

    for(i = 1, s = 0; i <= n; ++ i) scanf("%d", &a[i]);

    ans = 0;
    merge_sort(1, n);

    printf("%d", ans);

    return 0;

 }