参考资料：《算法入门经典训练指南》刘汝佳 P197
这本书上面写的题目大意、解题思路都写出来了。
在这我贴上自己的
AC代码：
#include<stdio.h>
#include<string.h> #define PEOPLE 20001
#define VALUE 100001 typedef long long LL; int n, a[PEOPLE], amin[PEOPLE], amax[PEOPLE], tree[VALUE]; int lowbit(int x){
return x & -x;
} void add(int x, int d){
while(x < VALUE){
tree[x] += d;
x += lowbit(x);
}
} int sum(int x){
int ret = ;
while(x > ){
ret += tree[x];
x -= lowbit(x);
}
return ret;
} int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = ; i <= n; ++i){
scanf("%d", &a[i]);
} memset(tree, , sizeof(tree));
for(int i = ; i <= n; ++i){
amin[i] = sum(a[i] - );//第i个人 统计在第i个人的左边并且技能值小于 的总人数
amax[i] = i - - amin[i];//统计 技能值大于第i个人并且在左边的总人数
add(a[i], );
} LL ans = ;
memset(tree, , sizeof(tree));
for(int i = n; i >= ; --i){
LL bmin = sum(a[i] - );//统计 技能值小于第i个人并且在第i个人的右边的总人数
ans += bmin * amax[i] + (n - i - bmin) * amin[i];
add(a[i], );
}
printf("%lld\n", ans);
}
return ;
}