poj 2299 Ultra-QuickSort（BIT求逆序数）

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 
9 1 0 5 4 ,
Ultra-QuickSort produces the output 
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0
解题思路：题意很简单，树状数组or归并排序求逆序数，这里只讲树状数组的实现！因为a[i]的值高达10^9，树状数组的大小肯定开不了这么大，而n最大为5e5（可作为数组大小，不过大小还要再开大一点，避免越界），因此需要将原来每个元素离散化，即重新编个号（1~n）。

做法：用一个结构体记录原来每个元素val出现的次序id，然后将结构体按val的大小升序排序，接下来遍历排序后的结构体数组，将原来的元素离散化成1~n，即将id对应原来的数字改成第i大(i∈[1,n])，最后就可以直接用树状数组进行更新和统计逆序数了。
拿题目中9 1 0 5 4这个样例来加强对数据离散化的理解：
输入的元素值    9  1  0  5  4   -->排序后   0  1  4  5  9
对应的次序id    1  2  3  4  5               3  2  5  4  1
此时将排序后每个id对应的元素离散化成第i小即 1  2  3  4  5，显然0是第1小，且是第3次出现，1是第2小，且是第2次出现...
这样我们就已经成功地把原来的数据离散化，接下来遍历一下次序id：tar[1]=5（原来为9，9是第一个输入的，这里就变成了5，空间上压缩了不少），先在树状数组中标记为1，并且5前面有4个空为0，于是5(9)这个元素构成了4个逆序对，累加逆序数4并继续按此操作下去即可找出所有的逆序数。
AC代码：

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=500005;
typedef long long LL;
int n,val,aa[maxn],tar[maxn];
struct node{int val,id;}nod[maxn];
bool cmp(node a,node b){return a.val<b.val;}
int lowbit(int x){
    return x & -x;
}
void update(int x,int val){
    while(x<=n){
        aa[x]+=val;
        x+=lowbit(x);
    }
}
int getsum(int x){
    int ret=0;
    while(x>0){
        ret+=aa[x];
        x-=lowbit(x);
    }
    return ret;
}
int main(){
    while(cin>>n&&n){
        LL ans=0;
        memset(aa,0,sizeof(aa));//注意清空
        for(int i=1;i<=n;++i){
            cin>>nod[i].val;
            nod[i].id=i;//记录元素val出现的次序id
        }
        sort(nod+1,nod+n+1,cmp);//然后数组元素val按升序排序
        for(int i=1;i<=n;++i)tar[nod[i].id]=i;//离散化数据：tar[nod[i].id]表示原来第nod[i].id次出现的值换成现在1~n中的编号i
        for(int i=1;i<=n;++i){
            update(tar[i],1);//tar[i]表示为输入值的次序：第i次出现的值（已离散化），先将该值在树状数组中标记为1，表示该数字已出现
            ans+=tar[i]-getsum(tar[i]);//求出tar[i]前面还没出现数字的个数即为与当前tar[i]构成逆序对的个数，然后累加即可
        }
        cout<<ans<<endl;
    }
    return 0;
}