hdu2689 Sort it (树状数组)

#include <stdio.h>  
#include <string.h>  
#define MAX 1002  

int arr[MAX],n;  
//树状数组  
int lowBit(int x)
{  
	return (x&(-x));  
}  

void add(int index)  
{  
	while(index<=n)  
	{  
		arr[index]++;  
		index+=lowBit(index);  
	}  
}  

int func(int num)  
{  
	int sum=0;  
	while(num>0)  
	{  
		sum+=arr[num];  
		num-=lowBit(num);  
	}  
	return sum;  
}  

int main()  
{  
	int i,ans,x;  
	while(scanf("%d",&n)!=EOF)  
	{  
		ans=0;  
		memset(arr,0,sizeof(arr));
		for(i=1;i<=n;i++)  
		{  
			scanf("%d",&x);   
			add(x);  
			ans+=(i-func(x));//求得的逆序数
		}  
		printf("%d\n",ans);
	}  
	return 0;  
}