# 题目链接

http://poj.org/problem?id=2299

# AC代码

```#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;
const int N=500100;
ll a[N],b[N];
int n;
ll ans;
struct TREE
{
int l,r;
ll sum;
}tree[N<<2];
void Build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].sum=0;
if(l==r)
return ;
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build(i<<1|1,mid+1,r);
tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
return ;
}
void Update(int i,int x)
{
if(tree[i].l==tree[i].r)
{
tree[i].sum++;
return ;
}
if(x<=tree[i<<1].r) Update(i<<1,x);
else Update(i<<1|1,x);
tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
return ;
}
int Query(int i,int l,int r)
{
if(l<=tree[i].l && tree[i].r<=r)
return tree[i].sum;
if(l>tree[i].r || r<tree[i].l) return 0;
int res=0;
if(tree[i<<1].r>=l) res+=Query(i<<1,l,r);
if(tree[i<<1|1].l<=r) res+=Query(i<<1|1,l,r);
return res;
}
int main()
{
while(scanf("%d",&n)&&n)
{
ans=0;//memset(tree,0,sizeof tree);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+n+1,a[i])-b;
Build(1,1,n);
for(int i=1;i<=n;i++)
{
Update(1,a[i]);
ans+=i-Query(1,1,a[i]);
}
printf("%lld\n",ans);
}
}
```