e<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+20;
int b[N],cnt;
//存原排列
struct node{
int x,id;
}a[N];
struct tnode{
int l,r,sum;
}tr[N<<2];
void pushup(int m)
{
tr[m].sum=tr[m<<1].sum+tr[m<<1|1].sum;
return;
}
void build(int m,int l,int r)
{
tr[m].l=l;
tr[m].r=r;
if(l==r)
{
tr[m].sum=0;
return;
}
int mid=(l+r)>>1;
build(m<<1,l,mid);
build(m<<1|1,mid+1,r);
pushup(m);
return;
}
void update(int m,int x)
{
if(tr[m].l==x&&tr[m].r==x)
{
tr[m].sum=1;
return;
}
int mid=(tr[m].l+tr[m].r)>>1;
if(x<=mid)
update(m<<1,x);
else
update(m<<1|1,x);
pushup(m);
return;
}
int query(int m,int l,int r)
{
if(tr[m].l==l&&tr[m].r==r)
return tr[m].sum;
int mid=(tr[m].l+tr[m].r)>>1;
if(r<=mid)
return query(m<<1,l,r);
if(l>mid)
return query(m<<1|1,l,r);
return query(m<<1,l,mid)+query(m<<1|1,mid+1,r);
}
bool cmp1(node p,node q)
{
return p.x<q.x;
}
bool cmp2(node p,node q)
{
return p.id<q.id;
}
int getid(int x)
{
return lower_bound(b,b+cnt,x)-b+1;
}
int main()
{
int n;
while(1)
{
scanf("%d",&n);
if(!n)
break;
//输入
a[0].x=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].id=i;
}
//先离散化
sort(a+1,a+n+1,cmp1);
cnt=0;
for(int i=1;i<=n;i++)
if(a[i].x!=a[i-1].x)
b[cnt++]=a[i].x;
//根据离散后的cnt建树
build(1,1,cnt);
//别忘了把a数组sort回来
sort(a+1,a+n+1,cmp2);
//边更新边查询
ll ans=0;
for(int i=1;i<=n;i++)
{
int t=getid(a[i].x);
ans+=query(1,t,n);
update(1,t);
}
//输出
printf("%lld\n",ans);
}
return 0;
}
|