Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 67681		Accepted: 25345

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.

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.

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.

5

9

1

0

5

4

3

1

2

3

0

6

0

思路;
树状数组裸题，逆序对思想，离散化处理
每插入一个点，查询下在这个点之前还有多少个点没被插入，这些点的数量就是逆序对的数量，也就是需要移动的步数
当然也可以用线段树写，只不过要多敲点。。
实现代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mid int m = (l + r) >> 1

const int M = 5e5 + ;

const double EPS = 1e-;

//inline int sgn(double x) return (x > EPS) - (x < -EPS); //浮点数比较常数优化写法

int b[M],c[M],n;

int lowbit(int x){

    return x&(-x);

}

int getsum(int x){

    int sum = ;

    while(x>){

        sum += c[x];

        x -= lowbit(x);

    }

    return sum;

}

void update(int x,int value){

    while(x<=n){

        c[x] += value;

        x += lowbit(x);

    }

}

struct node{

    int id,val;

}a[M];

bool cmp(node x,node y){

    return x.val < y.val;

}

int main()

{

    while(scanf("%d",&n)&&n){

        memset(c,,sizeof(c));

        for(int i = ;i <= n;i ++){

            scanf("%d",&a[i].val);

            a[i].id = i;

        }

        sort(a+,a+n+,cmp);

        for(int i = ;i <= n;i ++)

            b[a[i].id] = i;

        ll ans = ;

        for(int i = ;i <= n;i ++){

            update(b[i],);

            ans += i-getsum(b[i]);

        }

        cout<<ans<<endl;

    }

    return ;

}