逆序对模板

模板一：

#include<iostream>
using namespace std;
int a[1000001],b[1000001],rr,tem,t,s;__int64 ans;
void merg(int ll,int l,int r)
{
	rr=l-1,tem=ll,t=l,s=ll;
	while(ll<=rr&&t<=r)
		if(a[ll]<=a[t])
			b[tem++]=a[ll++];
		else 
		{
			ans+=l-ll;
			b[tem++]=a[t++];
		}
		while(ll<=rr) 
			b[tem++]=a[ll++];
		while(t<=r) 
			b[tem++]=a[t++];
		for(;s<=r;s++) 
			a[s]=b[s];
}
void mergsort(int l,int r)
{
	if(l<r)
	{
		int mid=(l+r)/2;
		mergsort(l,mid);mergsort(mid+1,r);
		merg(l,mid+1,r);
	}
}
void main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++) scanf("%d",&a[i]);
		ans=0;mergsort(1,n);
		printf("%I64d\n",ans);
	}
}

模板二：

#include<iostream>
using namespace std;
int a[1000001],b[1000001],rr,tem,t,s;__int64 ans;
void merg(int ll,int l,int r)
{
	rr=l-1,tem=ll,t=l,s=ll;
	while(ll<=rr&&t<=r)
		if(a[ll]<=a[t])
			b[tem++]=a[ll++];
		else 
		{
			ans+=l-ll;
			b[tem++]=a[t++];
		}
		while(ll<=rr) 
			b[tem++]=a[ll++];
		while(t<=r) 
			b[tem++]=a[t++];
		for(;s<=r;s++) 
			a[s]=b[s];
}
void mergsort(int l,int r)
{
	if(l<r)
	{
		int mid=(l+r)/2;
		mergsort(l,mid);mergsort(mid+1,r);
		merg(l,mid+1,r);
	}
}
void main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++) scanf("%d",&a[i]);
		ans=0;mergsort(1,n);
		printf("%I64d\n",ans);
	}
}