杭電2689 Sort it

題目連結：​​http://acm.hdu.edu.cn/showproblem.php?pid=2689​​

用樹狀數組求逆序數的題目

1、什麼是逆序數？

         在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大于後面的數，那麼它們就稱為一個逆序。一個排列中逆序數的總數就是這個排列的逆序數。

2、用樹狀數組求逆序數的總數

         2.1該背景下樹狀數組的含義

         我們假設一個數組A[n],當A[n]=0時表示數字n在序列中沒有出現過，A[n]=1表示數字n在序列中出現過。A對應的樹狀數組為c[n],則c[n]對應維護的是數組A[n]的内容，即樹狀數組c可用于求A中某個區間的值的和。

         樹狀數組的插入函數(假設為 void insert(int i,int x) )的含義：在求逆序數這個問題中，我們的插入函數通常使用為insert( i , 1 )，即将數組A[i]的值加1 (A數組開始應該初始化為0，是以也可以了解為設定A[ i ]的值為1，即将數字i 加入到序列的意思 )。，同時維護c數組的值。

         樹狀數組中區間求和函數(假設函數定義為： int getsun(int i ) )的含義：該函數的作用是用于求序列中小于等于數字 i 的元素的個數。這個是顯而易見的，因為樹狀數組c 維護的是數組A的值，則該求和函數即是用于求下标小于等于 i 的數組A的和，而數組A中元素的值要麼是0要麼是1，是以最後求出來的就是小于等于i的元素的個數。

         是以要求序列中比元素a大的數的個數，可以用i - getsum(a)即可( i 表示此時序列中元素的個數)。

         2.2如何使用樹狀數組求逆序數總數

         首先來看如何減小問題的規模:

         要想求一個序列 a b c d,的逆序數的個數，可以了解為先求出a b c的逆序數的個數k1，再在這個序列後面增加一個數d，求d之前的那個序列中值小于d的元素的個數k2，則k1+k2即為序列a b c d的逆序數的個數。

         舉個例子加以說明：

　　假設給定的序列為 4 3 2 1，我們從左往右依次将給定的序列輸入，每次輸入一個數temp時，就将目前序列中大于temp的元素的個數計算出來，并累加到ans中，最後ans就是這個序列的逆序數個數。

序列的變化(下劃線為新增加元素)	序列中大于新增加的數字的個數	操作
{ }	初始化時序列中一個數都沒有
{4 }	往序列中增加4，統計此時序列中大于4的元素個數
{4 3 }	1	往序列中增加3，統計此時序列中大于3的元素個數
{4 3 2}	2	往序列中增加2，統計此時序列中大于2的元素個數
{4 3 2 1}	3	往序列中增加1，統計此時序列中大于1的元素個數

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;
int C[maxn],n;
void add(int k,int num){
    while(k<=n){  
        C[k]+=num;  
        k+=k&-k;  
    }  
}  
int query(int i) {
    int sum=0;
    while(i>0)     {
        sum+=C[i];
        i-=i&-i;
    }
    return sum;
}
int main(){
    while(cin>>n){
        int sum=0;
        memset(C,0,sizeof(C));
        for(int i=1; i<=n; i++)         
        {
            int a;
            cin>>a;
            add(a,1);
            sum+=i-query(a);//得出比i大的的元素個數，即要交換的次數
        }
        cout<<sum<<endl;
    }
    return 0;
}