POJ2299 Ultra-QuickSort 树状数组

题目：

POJ2299

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

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

Source

题意：

给定一串序列，求将它按升序排列要交换几次。

思路；

题目就是要求该序列中有几个逆序对。

为了使数据更小更方便计算，计算前先将数据离散化。

关于离散化：

百科解释

在不需要用到数据的精确值而只用知道数据的相对大小时，可以这样处理。

如样例 9 1 0 5 4 可离散化成为 5 2 1 4 3。

//离散化部分代码
for(int i=1; i<=n; i++) {scanf("%d",&a[i].value);a[i].num=i;
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++) {b[a[i].num]=i;
}

要求该序列中有几个逆序对，可以求出每个数前面有几个数比自己大，再把每个数的值相加。要求每个数前面有几个数比自己大，可以先求出前面有几个数小于等于自己，在用自己的编号（该数在序列中的第几个编号就为几）减去这个值就是比自己大的数的个数。

树状数组c[x]中存的是小于等于数x的数的个数。

查询时把查到的值顺次相加返回即可。

输出i-查询到的值。

//树状数组部分代码 
int lowbit(int x){return (x&(-x));
}void add(int x) {while(x<=n){c[x]++;x+=lowbit(x);}return ;
}int getsum(int x) {int s=0;while(x>=1){s+=c[x];x-=lowbit(x);}return s;
}

还要注意，因为输出值很大，要用long long型输出。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int n;
struct A {int num;int value;bool operator < (const A& x) const {if(value<x.value) return true;if(value==x.value&&num<x.num) return true;return false;}
};int c[500010]= {0};int lowbit(int x){return (x&(-x));
}void add(int x) {while(x<=n){c[x]++;x+=lowbit(x);}return ;
}int getsum(int x) {int s=0;while(x>=1){s+=c[x];x-=lowbit(x);}return s;
}A a[500010]= {0};
int b[500010]= {0};
int main() {while(true) {scanf("%d",&n);if(n==0) break;memset(b,0,sizeof(b));memset(c,0,sizeof(c));for(int i=1; i<=n; i++) {scanf("%d",&a[i].value);a[i].num=i;}sort(a+1,a+n+1);for(int i=1; i<=n; i++) {b[a[i].num]=i;}long long s=0;for(int i=1; i<=n; i++) {add(b[i]);s+=i-getsum(b[i]);}printf("%lld\n",s);}return 0;
}