HDU 2689 sort it - from lanshui_Yang

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    題目大意：給你一個數n ，然後有1 ~ n 的一個排列，讓你找出這個排列的逆序數。    解題思路：此題可以用樹狀數組來解，樹狀數組的三個用途：1.單點更新，區間求和 2、區間更新，單點求和3、求逆序數。求逆序數想法較簡單，請看代碼

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std ;
const int MAXN = 1e5 + 7 ;
int C[MAXN] ;
int n ;
int lowbit(int x)
{
    return x & -x ;
}
int sum(int x)
{
    int sumt = 0 ;
    while (x > 0)
    {
        sumt += C[x] ;
        x -= lowbit(x) ;
    }
    return sumt ;
}
void add(int x , int d)
{
    while (x <= n)
    {
        C[x] += d ;
        x += lowbit(x) ;
    }
}
int main()
{
    while (scanf("%d" , &n) != EOF)
    {
        int i ;
        int ans = 0 ;
        memset(C , 0 ,sizeof(C)) ;
        for(i = 1 ; i <= n ; i ++)
        {
            int a ;
            scanf("%d" , &a) ;
            add(a , 1) ;  // 此處是整個程序的精華部分，請好好理解
            ans += i - sum(a) ;  // 統計逆序數
        }
        printf("%d\n" , ans) ;
    }
    return 0 ;
}