POJ3928、LA4329树状数组

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

这题为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;  
}  

补充：软件开发 , C++ ,

上一个：hdu1176 免费馅饼
下一个：POJ1837 Balance