学步园

题意：训练指南上的例题。大致求1到ai-1有多少个数小于ai；

树状数组，从第一个数开始处理，遇到一个数ai，将C[ai]赋值为1，插入树状数组。便可以快速和。但是bit的最高位要注意是所有输入的数中最大的。开始写成输入的数的个数，wa了好几次。

代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
#define size 100010
using namespace std;
int A[size],C[size],c[size],d[size],vv=0;
int bit(int x)
{
    return x&-x;
}
long long sum(int x)
{
    long long ret=0;
    while(x>0)
    {
        ret+=C[x];
        x-=bit(x);
    }
    return ret;
}
void add(int x,int n)
{
    while(x<=vv)
    {
        C[x]+=1;
        x+=bit(x);
    }
}
int main()
{
   int T;
   scanf("%d",&T);
   while(T--)
   {
       int N;
       long long count=0;
       scanf("%d",&N);
       memset(C,0,sizeof(C));
       for(int i=1;i<=N;i++)
       {
           scanf("%d",&A[i]);
            vv=max(vv,A[i]);
       }
       for(int i=1;i<=N;i++)
       {
           c[i]=sum(A[i]);
           add(A[i],N);

       }
       memset(C,0,sizeof(C));
       for(int i=N;i>=1;i--)
       {
           d[i]=sum(A[i]);
           add(A[i],N);
       }
      /* for(int i=1;i<=N;i++)
       {
           cout<<c[i]<<" ";
       }
       cout<<endl;
        for(int i=1;i<=N;i++)
       {
           cout<<d[i]<<" ";
       }
       cout<<endl;*/
       for(int i=1;i<=N;i++)
       {
           count+=c[i]*(N-i-d[i])+(i-c[i]-1)*d[i];
       }
       cout<<count<<endl;
   }
   return 0;
}