学步园

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tree[1001000],b[1001000],n;
struct node
{
	int value,no;
}arr[1001000];
int cmp(node x,node y)
{
	return x.value<y.value;
}
int LowBit(int x)
{
	return x&(-x);
}
__int64 GetSum(int x)
{
	__int64 temp=0;
	for(int i=x;i<=n;i+=LowBit(i))
		temp+=tree[i];
	return temp;
}
void UpDate(int x,int c)
{
	for(int i=x;i>=1;i-=LowBit(i))
		tree[i]+=c;
}
int main()
{
	while(scanf("%d",&n)!=EOF && n!=0)
	{
		memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++)
		{
			scanf("%d",&arr[i].value);
			arr[i].no=i;
		}
		sort(arr+1,arr+1+n,cmp);
		for(int i=1;i<=n;i++)
		{
			arr[arr[i].no].value=i;
		}
		for(int i=1;i<=n;i++)
		{
			b[i]=GetSum(arr[i].value);
			UpDate(arr[i].value,1);
		}
		__int64 ans=0;
		for(int i=1;i<=n;i++)
			ans+=b[i];
		printf("%I64d\n",ans);
	}
	system("pause");
	return 0;
}