训练指南上面的题目，树状数组,给出一个序列，从左到右表示每个人的值，问存在有多少对{i,j,k}满足Xi<Yj<Zk。

1 #include
     
       2 #include
      
        3 const int maxval=100000+5; 4 const int maxn=20000; 5 int val[maxn]; 6 int c[maxn]; 7 int b[maxn]; 8 int flag[maxval]; 9 int n;10 int lowbit(int x)11 {12     return x&(-x);13 }14 int sum(int x)15 {16     int ret=0;17     while(x>0)18     {19         ret+=flag[x];20         x-=lowbit(x);21     }22     return ret;23 }24 void add(int x,int d)25 {26     while(x<=maxval)27     {28         flag[x]+=d;29         x+=lowbit(x);30     }31 }32 int main()33 {34     int t;35     scanf("%d",&t);36     while(t--)37     {38         scanf("%d",&n);39         memset(flag,0,sizeof(flag));40         for(int i=1;i<=n;i++)41         {42             scanf("%d",&val[i]);43             add(val[i],1);44             c[i]=sum(val[i]-1);45         }46         for(int i=1;i<=n;i++)47             b[i]=sum(val[i]-1)-c[i];48         long long ans=0;49         for(int i=1;i<=n;i++)50             ans+=c[i]*(n-i-b[i])+(i-1-c[i])*b[i];51          printf("%I64d\n",ans);52     }53     return 0;54 }