不想用树状数组，我觉得归并排序更好写

#include<iostream>
using namespace std;
int n,a[500005],c[500005];
long long ans;
void MergeSort(int l, int r){
    if (l == r)
        return;
    int  mid, i, j, k;
    mid = (l + r) / 2;
    i = l;
    j = mid + 1;
    k = l;
    MergeSort(l, mid);
    MergeSort(mid + 1, r);
    while (i <= mid and j <= r){
        if (a[i] <= a[j])  c[k++]=a[i++];
        else c[k++]=a[j++],ans+=mid-i+1;
    }   
    while (i <= mid)c[k++] = a[i++];
    while (j <= r)c[k++] = a[j++];
    for (int t = l; t <= r; t++)
        a[t] = c[t];
} 
int main(){
	cin >> n; 
    for (int i = 1; i <= n; i++)
    	cin >> a[i];
    MergeSort(1, n);
    cout << ans;
    return 0;
}

可恶，为什么题解区没一个使用树状数组的

归并固然好用，树状数组也必须掌握。

这道题本质上就是在求每一个数前面有几个大于它的数，考虑树状数组。每输入一个 $a_i$ 就将 $c_{a_i}+1$ 并维护，这样 $\operatorname{sum}(a_i)$ 求的就是 $a_i$ 前面有多少个 $\le a_i$ 的数，那 $i-\operatorname{sum}(a_i)$ 就是 $a_i$ 前面有几个大于它的数，$a_i$ 对最终答案的贡献就求出来了。

这是一个值域上的树状数组。但是值域太大（$a_i \le 10^9$）数组存不下怎么办？离散化，我们只关心 $a_i$ 的大小关系。时间复杂度 $\Theta(n \log n)$

最后提一句：十年 OI 一场空——

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[500001],b[500001],c[500001];
ll ans;
void add(int x){
    for (int i=x;i<=n;i+=i&(-i)){
        c[i]++;
    }
}
ll sum(int x){
    ll cnt=0;
    for (int i=x;i;i-=i&(-i)){
        cnt+=c[i];
    }
    return cnt;
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for (int i=1;i<=n;i++){//按顺序存入 a[i]
        int k=lower_bound(b+1,b+n+1,a[i])-b;//离散化
        add(k);//将 a[i] 加入树状数组
        ans+=i-sum(k);
    }
    cout<<ans;
    return 0;
}

这道题用到的是归并排序分而治之的思想，所以我们先来回顾一下归并排序的概念。 先简单看一下归并排序的代码：

void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    
    merge_sort(q,l,mid);merge_sort(q,mid+1,r);
    
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(i=0,j=l;j<=r;i++,j++) q[j]=tmp[i];
}

先设立一个中心点mid，进行递归处理，将数组不断分成两，最后成为单一的元素，此为分。

然后既是让每一个元素符合我们的要求，也就是从小到大排序，此为治。

这是归并排序，既然归并排序把数组分为两段，我们再来看看逆序对的情况

逆序对的两个元素都在左端 逆序对的两个元素都在右端 一个元素在左端，一个元素在右端

我们是把q[i],q[j]进行比较，把较小的元素放到一个新数组t[]中。所以我们能保证i左边的元素都是小于j的，然后i右边的元素都是大于j的，所以对于q[j]来说，满足的元素有（mid-i+1）个。

所以我们只要在q[i]>q[j]的情况下，加上一个计数器res+=mid-i+1，就可以自然而然的完成我们的“治”，也就是寻找并记录下我们的逆序对。

#include<iostream>

using namespace std;

const int N=100010;
int q[N],t[N],n;
long long res;//假如按照逆序对最多的情况，也就是倒序，例：5 4 3 2 1。
				//int不能满足res。

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);//  “分”
    
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) t[k++]=q[i++];
        else
        {
            t[k++]=q[j++];
            res+=mid-i+1;//  “治”
        }    
    }
    while(i<=mid) t[k++]=q[i++];//收尾：假如左端或者右端先填完了，得把另一端的数都加上。
    while(j<=r) t[k++]=q[j++];
    
    for(i=l,j=0;i<=r;i++,j++) q[i]=t[j];
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++) cin >> q[i];
    
    merge_sort(0,n-1);
    cout << res << endl;
    
    return 0;
}

但是上面的代码只有50分 所以我就用了树状数组 树状数组求逆序对的过程用模拟好理解一些。是用树状数组维护一个桶，在for中扫一遍的过程就是i<j的过程，在桶中log（N)维护前缀和

下面放了一部分代码,防止抄袭

LL tree[maxn];
LL n;
struct P{
	LL val,index;
}a[maxn];
bool cmp(P A,P B){
	if(A.val==B.val) return A.index<B.index;
	return A.val<B.val;
}
LL add(LL x,LL d){
	while(x<=n){
		tree[x]+=d;
		x+=lowbit(x);
	}
}
LL sum(LL x){
	LL sum=0;
	while(x>0){
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n;
  for(LL i=1;i<=n;i++){
  	cin>>a[i].val;a[i].index=i;
  }
}

又通过一道题