朴素 BST，可以卡到 $O(n^2)$ （比如 1······n）。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
typedef long long ll;
ll n, cnt = 1, a[MAXN], b[MAXN];
struct BST{
	ll val, cnts, ls, rs, siz;
}tree[MAXN];
void update(int u, int x){
	if(x == tree[u].val)
		tree[u].cnts++;
	else if(x < tree[u].val){
		if(~tree[u].ls)
			update(tree[u].ls, x);
		else {
			tree[u].ls = ++cnt; 
			tree[cnt] = (BST){x, 1, -1, -1, 1};
		}
	}else {
		if(~tree[u].rs) 
			update(tree[u].rs, x);
		else {
			tree[u].rs = ++cnt;
			tree[cnt] = (BST){x, 1, -1, -1, 1};
		}
	}
	tree[u].siz++;
}
ll ranked(int u, ll x){// ranked 定义为 小于等于 x 的有多少 
	if(u == -1)
		return 0;
	if(x == tree[u].val){
		if(tree[u].ls != -1)
			return tree[tree[u].ls].siz + tree[u].cnts;
		return tree[u].cnts;
	}
	else if(x < tree[u].val)
		return ranked(tree[u].ls, x);
	else 
		return tree[tree[u].ls].siz + tree[u].cnts + ranked(tree[u].rs, x); 
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	ll ans = 0;
	tree[1] = (BST){a[1], 1, -1, -1, 1};
	for(int i = 2; i <= n; i++){
		update(1, a[i]);
		ans += i - ranked(1, a[i]);
	}
	cout << ans; 
	return 0;
}