nlogn，5e5的数据不至于600ms吧

//先把原数组离散化unique+lower_bound 
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
int a[1000010],b[1000010];
struct node{
	int l,r,sum;
}tree[4000010];
void build(int p,int l,int r)
{
	tree[p].l=l;
	tree[p].r=r;
	if(l==r)
	return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void update(int p,int c)//单点修改，把c这个数的位置++ 
{
	if(tree[p].l==tree[p].r)
	{
		tree[p].sum++;
		return ;
	}
	int mid=(tree[p].l+tree[p].r)>>1;
	if(c<=mid)
	update(p<<1,c);
	else update(p<<1|1,c);
	tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
int query(int p,int l,int r)//区间查询 
{
	if(l<=tree[p].l&&tree[p].r<=r)
	{
		return tree[p].sum;
	}
	int mid=(tree[p].l+tree[p].r)>>1;
	int res=0;
	if(l<=mid)
	res+=query(p<<1,l,r);
	if(r>mid)
	res+=query(p<<1|1,l,r);
	return res;
} 
int main()
{
	cin>>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;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	}
	build(1,1,m);
	for(int i=1;i<=n;i++)
	{
		ans+=query(1,a[i]+1,m);
		update(1,a[i]); 
	}
	cout<<ans;
	return 0;
}