题目链接：点击打开链接
树状数组求逆序数的一个模板题。
对于给定的序列，变为递增顺序，每个位置的数的交换次数即为该数组成的逆序对的个数，所以此类题转化为求每个位置的逆序对。num数组保存的为原始数据序列，a,b为树状数组，a用于正向遍历num,对于每个num[i],均从num[i]+1更新到n,即getSum(a,num[i])为比num[i]早出现的且小于num[i]的数的个数，即在该数左边且小于该数的数的个数；b用于反向遍历num,对于每个num[i],也是从num[i]+1更新到n,即getSum(b,num[i] -1)为反向比num[i]早出现的且小于num[i]的数的个数，即在该数右边且小于该数的数的个数；要想转化为逆序数，还要进行处理
// HDU 2838 Cow Sorting.cpp 运行：62ms
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
LL n,num[100005],a[100005],b[100005];
LL lowBit(LL x) {
return x & (-x);
}
LL getSum(LL a[],LL x) {
LL sum = 0;
while (x >= 1) {
sum += a[x];
x -= lowBit(x);
}
return sum;
}
void update(LL a[],LL x) {
while (x <= n) {
a[x]++;
x += lowBit(x);
}
}
int main(){
LL te,re = 0;
while (scanf("%lld", &n) != EOF) {
re = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (LL i = 1; i <= n; i++) {
scanf("%lld", &num[i]);
update(a, num[i]);
te = num[i] * (i - getSum(a, num[i]));//左边逆序数为i - getSum(a,num[i])
re += te;
}
for (int i = n; i >= 1; i--) {
te = num[i] * getSum(b,num[i] - 1);//右边逆序数为getSum(b,num[i] - 1)
re += te;
update(b, num[i]);
}
printf("%lld\n", re);
}
return 0;
}