线段树求改

#include <bits/stdc++.h>
#define LL long long
#define lc(i) ((i) << 1)
#define rc(i) (((i) << 1) | 1)
using namespace std;
const int N = 5e5 + 10;
int a[N];
struct node {
    int sum;
} tree[N << 2];
inline void update(int i, int tl, int tr, int pos) {
    if(tl == tr) {
        tree[i].sum++;
        return ;
    }
    int tmid = (tl + tr) >> 1;
    if(pos <= tmid) update(lc(i), tl, tmid, pos);
    else update(rc(i), tmid + 1, tr, pos);
    tree[i].sum = tree[lc(i)].sum + tree[rc(i)].sum;
}
inline LL query(int i, int tl, int tr, int l, int r) {
    if(l <= tl && r >= tr) return tree[i].sum;
    int tmid = (tl + tr) >> 1, lsum = 0, rsum = 0;
    if(l <= tmid) lsum = query(lc(i), tl, tmid, l, r);
    if(r > tmid) rsum = query(rc(i), tmid + 1, tr, l, r);
    return lsum + rsum;
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        LL sum = query(1, 1, n, a[i] + 1, n);
        ans += sum;
        update(1, 1, n, a[i]);
    }
    printf("%lld", ans);
    return 0;
}