788. 逆序对的数量

输入样例：

6
2 3 4 5 6 1

i < j && a[i] > a[j] 则称为逆序对。
如何用归并排序求逆序对的数量？
是基于分治的思想。

#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
int a[N],temp[N];
ll res = 0;
int merge_sort(int l,int r,int q[])
{
	if(l >= r ) return 0;
	int mid = l+r>>1;
	merge_sort(l,mid,q);
	merge_sort(mid+1,r,q);
	int i=l,j=mid+1,k=1;
	while(i<=mid && j<=r)
	{
		if(q[i] <= q[j])
		{
			temp[k++] = q[i++];
		}
		else temp[k++] = q[j++],res+=mid - i + 1;
	}
	while(i<=mid) temp[k++] = q[i++];
	while(j<=r) temp[k++] = q[j++];
	for(int i=l,k=1;i<=r;i++) q[i] = temp[k++];
	return res;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	merge_sort(1,n,a);
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714342.html