hdu 4000 Fruit Ninja(树状数组)

#include<stdio.h>
#include<string.h>
const int N=100000+5;
const int m=100000007;

int n,c[N];

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

void add(int x)
{
    while(x<=n)
    {
       c[x]+=1;
       x+=lowbit(x);
    }
}

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

int main()
{
    int cas=0,_,p;
    __int64 ans,t1,t2;
    scanf("%d",&_);
    while(_--)
    {
        scanf("%d",&n);
        memset(c,0,sizeof(c));

        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p);
            add(p);
            t1=sum(p-1);
            t2=n-p-(i-t1-1);

            ans-=t2*t1;

            if(t2>=2)
                ans+=t2*(t2-1)/2;

            //ans%=m;
        }

        printf("Case #%d: %I64d
",++cas,ans%m);
    }
    return 0;
}