树状数组 hdu2689

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e3+3;
int bit[M],n;
void update(int x,int c){
    while(x<=n)
        bit[x]+=c,x+=x&-x;
}
int sum(int x){
    int ans=0;
    while(x)
        ans+=bit[x],x-=x&-x;
    return ans;
}
int main(){
    while(~scanf("%d",&n)){
        int ans=0;
        memset(bit,0,sizeof(bit));
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            update(x,1);
            ans+=i-sum(x);//sum(x)表示小于等于x的总数，而i-sum()则表示大于x的总数，即为逆序数的总数
        }
        printf("%d\n",ans);
    }
    return 0;
}