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;  
}