请求加强数据

朴素 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;
}