写的归并

#include<bits/stdc++.h>
using namespace std;
long long a[1145140];
long long t[1145140];
long long ans=0;
long long bing(long long l1,long long r1,long long l2,long long r2){
	memset(t,0,sizeof t);
	long long l=l1,r=l2;
	long long o=1;
	while(l<=r1&&r<=r2){
		if(a[l]>a[r]){
			ans+=r-o+1-l1;
			t[o++]=a[r];
			r++;
		}
		else{
			t[o++]=a[l];
			l++;
		}
	}
	while(l<=r1){
		t[o++]=a[l++];
	}
	while(r<=r2){
		t[o++]=a[r++];
	}
	for(long long i=l1,j=1;i<=r2;i++,j++){
		a[i]=t[j];
	}
}
void g(long long l,long long r){
	if(l>=r) return;
	long long mid=(l+r)>>1;
	g(l,mid);
	g(mid+1,r);
	bing(l,mid,mid+1,r);
}
int main(){
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
	}
	g(1,n);
	cout<<ans;
	return 0;
}