HDOJ 2689

Sort it Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1940    Accepted Submission(s): 1390     Problem Description You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.     Input The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.     Output For each case, output the minimum times need to sort it in ascending order on a single line.     Sample Input 3 1 2 3 4  4 3 2 1      Sample Output 0 6     Author WhereIsHeroFrom     Source ZJFC 2009-3 Programming Contest     Recommend yifenfei   題意是給你一個序列，問你最少交換多少次可以使整個序列單調上升。 數據只有1000，直接n^2可做，但是有一種更為精妙的方法——樹狀數組 0Ms 我們先初始化整個序列為0，然後每輸入一個數x，就在x位置將0換成1，此時求該位置的sum，就是比x小的數字數目，顯然i - sum就是是這個數字要交換的次數。

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
int a[1010], c[1010] , n;  
int lowbit(int x)  
{  
    return x & (-x);  
}  
int sum(int x)  
{  
    int sum = 0;  
    while(x > 0)  
    {  
        sum += c[x];  
        x -= lowbit(x);  
    }  
    return sum;  
}  
void update(int x , int num)  
{  
    while(x <= n)  
    {  
        c[x] += num;  
        x += lowbit(x);  
    }  
}  
int main()  
{  
    while(~scanf("%d" , &n))  
    {  
        memset(a , 0 , sizeof(a));  
        memset(c , 0 , sizeof(c));  
        int ans = 0;  
        int x;  
        for(int i = 1 ; i <= n ; i++)  
        {  
            scanf("%d" , &x);  
            update(x , 1);  
            ans += i - sum(x);  
        }  
        printf("%d\n" , ans);  
    }  
    return 0;  
}