逆序数 （C++代码）分治算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[50005],b[50005];
ll ans;
ll n;
void gui(ll L,ll min,ll r)
{
	ll i=L,j=min;
	ll k=L;
	while(i<min&&j<r)
	{
		if(a[i]<a[j]) b[k++]=a[i++];
		else {
			ans=ans+min-i;
			b[k++]=a[j++];
		}
	}
		while(i<min)
		{
			b[k++]=a[i++];
		}
		while(j<r)
		{
			b[k++]=a[j++];
		}
	
	for(int i=L;i<r;i++)
			a[i]=b[i];
}
void f(ll L,ll r)
{
	if(L+1<r)
	{
		
		ll min=(L+r)/2;
		f(L,min);
		f(min,r);
		gui(L,min,r);
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	f(0,n);
	
	cout<<ans<<endl;
	return 0;
}

解题思路:

注意事项:

参考代码: