链接：https://vjudge.net/problem/UVA-1428
思路：刚学树状数组，完全没有看出来这是一个树状数组的题，关键是要统计左边比他大和小的人数，这时候不应该用人来建立区间，而是应该用能力值去建立区间，然后每加入一个能力值就统计1-当前能力值-1的所有的和（即为比他小的人数和）。必须每加一个就统计算出当前的（不然后面加入后人数就发生了改变，就不是他左边的比他小的人数了），然后再从右往左算一次，最后用乘法原理求和即可，很妙但是感觉自己还没能完全理解这种转化思想，先写在这里慢慢领悟把。
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n;
const int maxn = 1e5+10;
int c[maxn],l[maxn],r[maxn],a[maxn];
int lowbit(int x){
return x&(-x);
}
void add(int x,int d){
while(x<maxn){
c[x]+=d;//c[x]表示当前x能力值的人数有多少。
x+=lowbit(x);
}
}
int sum(int x){
int res = 0;
while(x>0){
res+=c[x];
x-=lowbit(x);
}
return res;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&t);
while(t--){
memset(c,0,sizeof(c));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
add(a[i],1);
l[i] = sum(a[i]-1);//统计当前左边的比他能力值小的人的总和
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
add(a[i],1);
r[i] = sum(a[i]-1);//统计当前右边的比他能力值笑的人的总和
}
long long ans = 0;
for(int i=2;i<=n;i++){
ans+=l[i]*(n-i-r[i])+(i-l[i]-1)*r[i];
}
printf("%lld\n",ans);
}
return 0;
}
