UVALive 4329 Ping pong

题意：

n个乒乓球爱好者住在大街上，每个人都有一个不同的技能值，组织一场比赛要三个人：两个选手，一个裁判。裁判必须住在选手中间，技能值在选手之间，问一共能组织多少种比赛。

Input

　　3 1 2 3

Output

思路：

考虑第i个人当裁判的情形，假设a1到ai-1中有c1i个比ai小，那么就有（i-1）-c1i个比ai大；同理，假设ai+1到an中有d1i个比ai小，那么就有（n-i）-d1i个比ai大。所以i当裁判有c1i（n-i-d1i）+（i-c1i-1）d1i种比赛，把他们加起来就是答案了。
c1i可以这样算：对于每一个ai，c1i=c1+.....+c（ai-1）（ai之前的数就把对应的数组c的值置为1），相当于是要求一个前缀和，所以用BIT来做比较方便。
d1i同理，只不过是从后往前处理。

代码：

#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;

const int maxn=2e5+5;
int t,n,ma,a[maxn],c[maxn],c1[maxn],d1[maxn];

int lowbit(int x){
   return x&-x;
}

int Sum(int x){
   int ret=0;
   while(x>0){
       ret+=c[x];
       x-=lowbit(x);
   }
   return ret;
}

void add(int x,int d){
   while(x<=ma){ //BIT数组中最大是ma，一开始没注意，wa了几发
       c[x]+=d;
       x+=lowbit(x);
   }
}

int main(){
   cin>>t;
   while(t--){
       cin>>n;
       ma=0;
       for(int i=1;i<=n;i++){
           cin>>a[i];
           ma=max(ma,a[i]);
       }
       memset(c,0,sizeof(c));
       memset(c1,0,sizeof(c1));
       memset(d1,0,sizeof(d1));
       for(int i=1;i<=n;i++){
           add(a[i],1);
           c1[i]=Sum(a[i]-1);
       }
       memset(c,0,sizeof(c));
       for(int i=n;i>=1;i--){
           add(a[i],1);
           d1[i]=Sum(a[i]-1);
       }
       long long sum=0;
       for(int i=2;i<=n-1;i++){
           sum+=(1LL*c1[i]*(n-i-d1[i])+(i-c1[i]-1)*d1[i]*1LL);
       }
       cout<<sum<<endl;
   }
   return 0;
}