学步园

一个数列通过两两相邻的数进行交换得到一个升序的数列需要交换的次数，等于这个数列的逆序数

逆序数：例如数列｛3，1｝，｛3，1，2｝这两个数列的逆序数各位1和2

这里数据太大，通过离散化进行树状数组求逆序数。

离散化：通过排序和映射即可实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 500000
struct hehe
{
	int pos,val;
	friend bool operator <(hehe a,hehe b)
	{
		return a.val<b.val;
	}
}b[MAX];
int a[MAX],n;
void update(int i,int val)
{
	while(i<=n)
	{
		a[i]+=val;
		i+=-i&i;
	}
}
int sum(int i)
{
	int sum=0;
	while(i>0)
	{
		sum+=a[i];
		i-=-i&i;
	}
	return sum;
}
int main()
{
	long long sum1;
	int i;
	while(scanf("%d",&n)&&n!=0)
	{
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&b[i].val);
			b[i].pos=i;
		}
		sum1=0;
		sort(b+1,b+n+1);
		for(i=1;i<=n;i++)
		{
			sum1+=sum(n)-sum(b[i].pos);
			update(b[i].pos,1);
		}
		printf("%lld\n",sum1);
	}
}