归并求逆序对【模板】

const int maxn = 5e5 + 10;
int arr[maxn];
int tmp[maxn];
ll merge(int l,int r)
{
	if(l == r) return 0;
	ll ans=0;
	int mid = l + r >> 1;
	ans+=merge(l,mid),ans+=merge(mid+1,r);
	int i = l,j = mid + 1,k=l;
	while(i<=mid && j<=r){
		if(arr[i]<=arr[j]){
			tmp[k++]=arr[i++];
		}
		else{
			tmp[k++]=arr[j++],ans+=mid-i+1;
		}
	}
	while(i<=mid) tmp[k++]=arr[i++];
	while(j<=r) tmp[k++]=arr[j++];
	for(i=l;i<=r;i++){
		arr[i]=tmp[i];
	}
	return ans;
}