借此题试验一下各种做法的效果~

这题为ACM2008北京站某题，介于简单与中等之间，做出来，罚时不多基本可以铜了，所以这样的题还必须得会，进阶之路。

add(a[i]+1,1)这样处理之后，再用sum(a[i])计算得出的便的确是比a[i]小的数目。结合树状图进一步了解下。

树状数组异常的美妙~

add(a[i],1)后树状数组的改变或许很复杂。。

嗯嗯！！明白了。

若换成add(a[i],1)后结果要相应换为sum(a[i])-1;就相当于在a[i]处多加了1，后面的就相当于add(a[i]+1,1)呗~~，但耗时会增多30+MS

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

const int maxn=100005;

long long  c[maxn];

int a[20005];

long long temp[maxn];

int lowbit(int x)

{

    return x&-x;

}

void add(int x,int y)

{

    while(x<=maxn)

    {

       c[x]+=y;

       x+=lowbit(x);

    }

}

long long sum(int x)

{

    long long ret=0;

    while(x>0)

    {

        ret+=c[x];

        x-=lowbit(x);

    }

    return ret;

}

int main()

{

    int case_num;

    scanf("%d",&case_num);

    while(case_num--)

    {

        memset(c,0,sizeof(c));

        int n;

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            add(a[i]+1,1);//自己再试一下只能0 1值的数组，结果类似，把+1换成+x[i]

            temp[i]=sum(a[i]);//这地方减c[x]对不对。。

        }

        long long ans=0;

        for(int i=1;i<=n;i++)

           printf(" %d ",sum(a[i]));

        printf("\n");

        for(int i=2;i<n;i++)

        {

            ans+=temp[i]*(n-i-(sum(a[i])-temp[i]));//其实一开始sum(a[i])-temp[i]还不太确定

            ans+=(i-1-temp[i])*(sum(a[i])-temp[i]);//我这个sum(a[i])到底包括本身不(不包括)

        }

        printf("%lld\n",ans);

    }

    return 0;

}