方法一：归并排序求逆序对

首先我们给出逆序对的定义：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，这里我们可以使用分治法解决问题。

我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；
因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。

比如序列是这样的
4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = 2T(n/2)+O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=1e5+1000;
int cnt;
int a[maxn],ans[maxn];
int n;
int gb(int l,int r)
{
    if(l>=r) return 0;
    int mid=l+r>>1;
    gb(l,mid),gb(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            ans[k++]=a[i++];
        }
        else
            ans[k++]=a[j++],cnt+=(mid-i+1);
    }
    while(i<=mid) ans[k++]=a[i++];
    while(j<=r) ans[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++){
        a[i]=ans[j];
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i,j;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    gb(0,n-1);
    cout<<cnt<<endl;
    return 0;
}

树状数组实现逆序对

树状数组不了解可以自行去补一下，非常好用的数据结构！
首先对序列进行离散化
先排序，再去重，使 b[1]到 b[m]是严格单调递增的整数序列，并包含了 a 数组中的每一个数

find(a[i])返回整数 a[i] 在 b 数组中的下标

然后从前往后遍历 a 数组，树状数组维护 ≤b[i]的数有几个
对于每一个 a[i] 我们需要知道前面有几个数大于它
可以用前面的数的个数减去≤a[i] 的数的个数，累加到答案里
res += sum(m) - sum(find(a[i]))
然后再往树状数组里加一个 a[i]就可以了

时间复杂度 O(nlogn)

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
int a[N], b[N];

int find(int x)
{
    int l = 1, r = m;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(b[mid] >= x)  r = mid;
        else l = mid + 1;
    }
    return l;
}

int tr[N];

void add(int x)
{
    for(int i = x; i <= m; i += i & -i)  tr[i] ++;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= i & -i)  res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]),  b[i] = a[i];

    sort(b + 1, b + n + 1);

    m = 1;
    for(int i = 2; i <= n; i ++)
        if(b[i] != b[m])  b[++ m] = b[i];

    LL res = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x = find(a[i]);
        res += sum(m) - sum(x);
        add(x);
    }
    printf("%lld", res);
    return 0;
}

题解 | #数组中的逆序对#

方法一：归并排序求逆序对

树状数组实现逆序对