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
题意就是输入一个n，接着输入n个数，然后求出这n个数的逆序数。
最简单的求逆序数就是用冒泡排序，每次比较，如果交换说明整两个数是逆序的，ans++，也就是说冒泡排序交换次数就是逆序数；但是时间复杂度是O(n^2).
再就是可以用归并排序来求逆序数，隐隐约约记得之前做过一道题是可以的来求的，虽然现在忘了啊。
这里用树状数组来求。
先说离散化
如果数据量少，但是数据范围大，那么开数组的话会浪费很大一部分空间，所以需要离散化处理(通俗点就是把离散较大的数据紧凑起来)
for (int i=1; i<=n; i++){
scanf("%d", &init[i].val);
init[i].order=i;
}
sort(init+1, init+n+1, cmp);
for (int i=1; i<=n; i++)
a[init[i].order]=i;
这样最后a数组的下标就是原来数据的元素的order位置，值就是被处理后的值。从而做到把离散的数据紧凑起来，节省空间。
这样就是把9 1 0 5 4变成5 2 1 4 3
再说求逆序数
这里用树状数组来求，就是每个元素的前面比它大的数量的和就是最终的逆序数。
在说明一点，i-sum(a[i])是本来一共有i个数，sum(a[i])是所有小于等于a[i]的个数，相减就是大于a[i]的个数，也就是在新的数前面大于它的元素的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int a[500005];
int c[500005];
struct node{
int order;
int val;
}init[500005];
int cmp(node a, node b){
return a.val<b.val;
}
int lowbit(int x){
return x&(-x);
}
void update(int index, int val){
while (index<=n){
c[index]+=val;
index+=lowbit(index);
}
}
int sum(int index){
int ans=0;
while (index>=1){
ans+=c[index];
index-=lowbit(index);
}
return ans;
}
int main(){
while (scanf("%d", &n) && n){
for (int i=1; i<=n; i++){
scanf("%d", &init[i].val);
init[i].order=i;
}
sort(init+1, init+n+1, cmp);
for (int i=1; i<=n; i++)
a[init[i].order]=i;
memset(c, 0, sizeof(c));
long long ans=0;
for (int i=1; i<=n; i++){
update(a[i], 1);
ans+=(i-sum(a[i]));
}
printf("%lld\n", ans);
}
return 0;
}
