HDOJ-2689 Sort it(树状数组模板)

Description：

hyh最近有点无聊，于是想出了一个游戏玩：给出一个数字序列，每次操作只能交换相邻两个数字，需要多少次才能使数字序列按升序来排。

Hint：例如1 2 3 5 4，我们只需要一个操作：交换5和4。

Sample Input

3
1 2 3
4 
4 3 2 1 

 

Sample Output

0
6

 代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) (x & (-x)) //树状数组的核心
using namespace std;

const int Maxn = 5005;
int a[Maxn],Tree[Maxn],n;

void update(int x,int k){   //修改子集和
    while(x <= n){ //修改下一个Tree[i]
     Tree[x]+=k;
     x += lowbit(x);
    }
}

int getsum(int x){   //查询前缀和
    int ans = 0;
    while( x >= 1){ //得到下一个Tree[x]并相加
        ans += Tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int read(){  //快读
    int s = 1,x=0;
    char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-')  s=-1; ch=getchar();}
    while(isdigit(ch))  { x = 10*x + ch - '0'; ch = getchar();}
    return x*s;
}

int main(){
    while(~scanf("%d",&n)){
        int ans = 0;
        memset(Tree,0,sizeof(Tree));
        for(int i=1 ;i<=n ;i++){
            a[i] = read();
            update(a[i],1);
            ans += (i-getsum(a[i])); 
        }
        printf("%d
",ans);
    }
}