一看到这个就应该能想到逆序对把。。。。
我的第一想法就是，假如我们现在在考虑第i个数字，我们需要统计在[1,i-1]里面有多少个数字大于A[i],以及[1,i-1]中大于A[i]的数字之和
大于A[i]的数字之和相当于X的积累，[1,i-1]里面有多少个数字大于A[i]记为m，第i个数字至少要交换m次，m*A[i]就相当于Y的积累
然后再全部积累一下，，这题就做完了
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;LL A[MX], B[MX];LL sum(LL *S, int x) {LL ret = 0;for(; x; x -= x & -x) {ret += S[x];}return ret;
}LL query(LL *S, int L, int R) {return sum(S, R) - sum(S, L - 1);
}void update(LL *S, int x, int d) {for(; x < MX; x += x & -x) {S[x] += d;}
}int main() {//freopen("input.txt", "r", stdin);int n, t;while(~scanf("%d", &n)) {memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));scanf("%d", &t);update(A, t, 1);update(B, t, t);LL ans = 0;for(int i = 2; i <= n; i++) {scanf("%d", &t);ans += query(A, t + 1, MX - 1) * t;ans += query(B, t + 1, MX - 1);update(A, t, 1);update(B, t, t);}printf("%I64d\n", ans);}return 0;
}