https://www.luogu.com.cn/problem/P1908
#include <bits/stdc++.h>
using namespace std;
#define lson root<<1
#define rson root<<1|1
#define MID int m = (l + r) / 2
const int MAX = 500005;
int data[MAX], tree[MAX<<2],t[MAX];
void build(int root, int l, int r) {
if (l == r) {
tree[root] = 0;
return;
}
MID;
build(lson, l, m);
build(rson, m+1, r);
tree[root] = tree[lson] + tree[rson];
}
void updata(int root, int l, int r, int pos) {
if (pos < l || pos > r)
return;
if (l == r) {
tree[root]++;
return;
}
MID;
updata(lson, l, m, pos);
updata(rson, m+1, r, pos);
tree[root] = tree[lson] + tree[rson];
}
long long query(int root, int l, int r, int ql, int qr) {
if (qr < l || r < ql)
return 0;
if (ql <= l && r <= qr) {
return tree[root];
}
MID;
return query(lson, l, m, ql, qr) + query(rson, m+1, r, ql, qr);
}
int main() {
// freopen("P1908_6.in","r",stdin);
int n;
scanf("%d", &n);
build(1, 1, n);
long long sum = 0;
//printf("OK\n");
for(int i=1;i<=n;i++){
scanf("%d",&data[i]);
//cout<<data[i]<<endl;
t[i] = data[i];
}
// printf("OK\n");
sort(t + 1, t + n + 1);
int m = unique(t + 1, t + 1 + n) - t - 1;
for(int i=1;i<=n;i++) data[i] = lower_bound(t + 1, t + 1 + m, data[i]) - t;
for (int i = 1; i <= n; i++) {
sum += query(1, 1, n, data[i]+1,n);
updata(1, 1, n, data[i]);
}
printf("%lld\n", sum);
}