借此题试验一下各种做法的效果~
这题为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;
}