原题链接：http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1020&ojid=1&cid=11842&hide=1&problem=Problem%20%20U
原题：
Problem 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
Ultra-QuickSort produces the output
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
题意：给出n和n个数，每次只能交换相邻两个元素，求多少次交换后能使这些数升序排列。
思路：典型的求逆序数的问题。由于数组元素可能过大，所以需要用到树状数组离散化。
源代码：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define MAX 500010
using namespace std;
int C[MAX];
int b[MAX];//备用数组，用于储存初始数组重新赋值后的结果
int lowbit(int x)
{return x &(-x);
}
int getsum(int x)
{int res = 0;while (x > 0){res += C[x];x -= lowbit(x);}return res;
}
void add(int x,int v)
{while (x < MAX){C[x] += v;x += lowbit(x);}
}
struct Point//用于储存该点的值及其初始位置
{int v;int id;
}point[MAX];
bool cmp(Point a,Point b)
{return a.v < b.v;
}
int main()
{int n;while (scanf("%d",&n)!=EOF){if (n == 0)break;for (int i = 1; i <= n; i++){scanf("%d",&point[i].v);point[i].id = i;}sort (point+1,point + n + 1,cmp);memset(b,0,sizeof(b));memset(C,0,sizeof(C));//初始值一定为0b[point[1].id] = 1;for (int i = 2; i <= n; i++)//数组离散化{if (point[i].v == point[i-1].v)b[point[i].id] = b[point[i-1].id];elseb[point[i].id] = i;}//for (int i = 1; i <= n; i++)// cout << b[i] << " ";//cout << endl;long long ans = 0;for (int i = 1; i <= n; i++)//求逆序数{add(b[i],1);ans += getsum(n) - getsum(b[i]);// cout << ans << endl;}//for (int i = 1; i <= n; i++)// cout << C[i] << " ";//cout << endl;printf("%lld\n",ans);}return 0;
}