线段树

#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define lc p<<1
#define rc p<<1|1
#define LL long long
struct tree{
    int l,r;
    LL sum;
}t[N<<2];
void pushup(int p){
    t[p].sum=t[lc].sum+t[rc].sum;
}
void build(int p,int l,int r){
    t[p]={l,r,0};
    if(l==r)return;
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
void update(int p,int x){
    if(t[p].l==x&&t[p].r==x){
        t[p].sum++;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)update(lc,x);
    else      update(rc,x);
    pushup(p);
}
LL query(int p,int x,int y){
    if(x<=t[p].l&&t[p].r<=y){
        return t[p].sum;
    }
    int mid=t[p].l+t[p].r>>1;
    LL res=0;
    if(x<=mid)res+=query(lc,x,y);
    if(mid<y)res+=query(rc,x,y);
    return res;
}
int a[N],b[N],n,m;
LL ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    build(1,1,m);
    for(int i=n;i>0;i--){
        int id=lower_bound(b+1,b+1+m,a[i])-b;
        update(1,id);
        ans+=query(1,1,id-1);
    }
    printf("%lld",ans);
    return 0;
}