Uva(1428)(Ping pong)

链接：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;
}