逆序对

离散化处理：排序，编号，便于装桶
树状数组：优化前缀和，每次存入后计算一下后面一共有多少个数即可
最后输出答案即可

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1048576;
int n,a[N],c[N],lns[N],len,ans;
int lowbit(int n){
	return n&(-n);
}
int get(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=c[i];
	return res;
}
void add(int x,int ind){
	for(int i=x;i<N;i+=lowbit(i))c[i]+=ind;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lns[i]=a[i];
	}
	sort(lns+1,lns+n+1);
	len=unique(lns+1,lns+n+1)-lns-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lns+1,lns+len+1,a[i])-lns;
	//离散化完成，接下来装桶，前缀和（树状数组优化）来求多少逆序对已有
	for(int i=1;i<=n;i++){
		add(a[i],1);
		ans+=get(n)-get(a[i]);
	}
	cout<<ans;
	return 0;
}