法一：归并排序

利用归并的思想实现的排序方法，该算法采用经典的分治策略
(分治法将问题分成一些小的问题然后递归求解，而分治的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10; 
int n;
int a[N],tmp[N];
ll res;

ll merge_sort(int l, int r)
{    
    if(l>=r) return 0; 

    int mid= l + r >> 1; 
    merge_sort(l,mid);  
    merge_sort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r){
        if(a[i]<=a[j]){
            tmp[k++] = a[i++];
        }
        else{
            tmp[k++] = a[j++];
            res += mid - i + 1;
            //保存右半部分的数，说明那个数要跳跃mid - x + 1个到前面来
        }
    }
    while(i<=mid) tmp[k++] = a[i++];
    while(j<=r) tmp[k++] = a[j++];
    for(i=l,j=0;i<=r;i++,j++){
        a[i]=tmp[j];
    } 
    return res;
}
int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    cout << merge_sort(0,n-1)<<endl;
    return 0;
}
/*
a[i]  4 5 1 3 2
res   0 0 2 2 3
*/

法二：树状数组

//采用冒泡排序所需要的swap次数=A中逆序对的个数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,a,sum[N];
typedef long long ll;
ll res;

//非负整数 x 在二进制表示下最低位 1 以及后面的0构成的数值
//原码和补码按位与
//按位与：只有对应的两个二进位都为1时，结果位才为1
int lowbit(int x){
    return x&(-x);
}

//sum[x] 保存以 x 为根的子树中叶结点的和
//sum[x] 覆盖的长度就是lowbit(x)  
void update(int x,int y){
    while(x<=n){
        sum[x]+=y;
        x+=lowbit(x);//追溯其父节点的下标
    }
}
int summ(int i){
    int ans= 0;
    while(i>0){
        ans+=sum[i];
        i-=lowbit(i);
    }
    return ans;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a;
        update(a,1);
        res+=i-summ(a);
    }
    cout<<res<<endl;
    return 0;
}