【树状数组+简单题】杭电 hdu 2689 Sort it

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2689
    Name  : 2689 Sort it

    Date  : Saturday, October 8, 2011
    Time Stage : half an hour

    Result: 
4722905	2011-10-08 21:19:56	Accepted	2689
15MS	240K	1078 B
C++	pyy


Test Data :

Review :
果然是比较水的题，当然，一开始有点犯蒙，看了下解题报告，
原来是跟逆序数对有关的，自己竟联系不起来，还想着把它们
逐一对换排序呢……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define INF		0x7f7f7f7f

#define MAXSIZE 1010

int n ;
int tree[MAXSIZE] ;

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

void add (int pos, int val)
{
	while (pos <= n)
	{
		tree[pos] += val ;
		pos += lowbit (pos) ;
	}
}

int getSum (int pos)
{
	int sum = 0 ;
	while (pos > 0)
	{
		sum += tree[pos] ;
		pos -= lowbit (pos) ;
	}
	return sum ;
}

int main ()
{
	int i, j ;
	int x, sum ;
	while (scanf ("%d", &n) != EOF)
	{
		memset (tree, 0, sizeof (tree)) ;
		sum = 0 ;
		for (i = 1 ; i <= n ; ++i)
		{
			scanf ("%d", &x) ;
			sum += getSum (n) - getSum (x) ;
			add (x, 1) ;
		}
		printf ("%d\n", sum) ;
	}
	return 0 ;
}