学步园

树状数组求逆序数 看了这位大牛的题解才茅塞顿开：http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

首先离散化，再求逆序数.

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <malloc.h>

using namespace std;

struct qq
{
	int x;
	int pos;
}a[500005];

int c[500005];
int b[500005];
int n;

bool cmp(qq a ,qq b)
{
	return a.x < b.x;
}

int lowbit(int i)
{
	return i&-i;
}

int sum (int i)
{
	int ans = 0;
	while (i>0)
	{
		ans += b[i];
		i-=lowbit(i);
	}
	return ans;
}

void updown(int i)
{
	while (i<=n)
	{
		b[i] += 1;
		i+=lowbit(i);
	}
}

int main ()
{
	while (scanf ("%d",&n)!=EOF && n!=0)
	{
		
		for (int i=1 ;i<=n;i++)
		   {
			   scanf ("%d",&a[i].x);
			   a[i].pos=i;
		   }

		 sort (a+1,a+1+n,cmp);

		 for (int i=1 ;i<=n;i++)
			c[a[i].pos]=i;
		
		memset (b,0,sizeof (b));

		long long  ans = 0;
		for (int i =1 ;i<=n;i++)
		{
			updown(c[i]);
			ans += i-sum(c[i]);
		}

		printf("%I64d\n",ans);
	}
	return 0;
}