萌新求助

只有25分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 100005;
struct ST
{
    int lc, rc;//左右子结点的编号
    //这个点上是否有数
    LL dat;
}tr[N];

int root, tot;
int build()
{
    ++tot;
    tr[tot].lc = tr[tot].rc = tr[tot].dat = 0;
    return tot;
}

//在val位置上的值加上delta，同时维护区间和
void insert(int p, int l, int r, int val)
{
    if (l == r)
    {
        tr[p].dat = 1;
        return;
    }
    int mid = l + r >> 1;
    if (val <= mid)
    {
        if (!tr[p].lc) tr[p].lc = build();
        insert(tr[p].lc, l, mid, val);
    }
    else
    {
        if (!tr[p].rc) tr[p].rc = build();
        insert(tr[p].rc, mid + 1, r, val);
    }
    tr[p].dat = tr[tr[p].lc].dat + tr[tr[p].rc].dat;
}

//查询区间[L, R]
LL sum(int p, int l, int r, int L, int R)
{
    if (L <= l && R >= r)
    {
        return tr[p].dat;
    }
    int mid = l + r >> 1;
    LL res = 0;
    if (mid >= L && tr[p].lc) res += sum(tr[p].lc, l, mid, L, R);
    if (mid < R && tr[p].rc) res += sum(tr[p].rc, mid + 1, r, L, R);
    return res;
}

int main()
{
    //n个点
    int n;
    scanf("%d", &n);

    //根节点
    root = build();
    LL res = 0;
    int x;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &x);
        res += sum(1, 1, 1e9, x + 1, 1e9);
        insert(1, 1, 1e9, x);
    }
    printf("%lld\n", res);

    return 0;
}