POJ 2299 Ultra-QuickSort(归并排序·树状数组·逆序对)

http://poj.org/problem?id=2299

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

http://www.acmerblog.com/POJ-2299-Ultra-QuickSort-blog-679.html

我们来看一个归并排序的过程:
给定的数组为[2, 4, 5, 3, 1]，二分后的数组分别为[2, 4, 5], [1, 3]，假设我们已经完成了子过程，现在进行到该数组的“并”操作：

a: [2, 4, 5]		b: [1, 3]		result:[1]		选取b数组的1
a: [2, 4, 5]		b: [3]		result:[1, 2]		选取a数组的2
a: [4, 5]		b: [3]		result:[1, 2, 3]		选取b数组的3
a: [4, 5]		b: []		result:[1, 2, 3, 4]		选取a数组的4
a: [5]		b: []		result:[1, 2, 3, 4, 5]		选取a数组的5

在执行[2, 4, 5]和[1, 3]合并的时候我们可以发现，当我们将a数组的元素k放入result数组时，result中存在的b数组的元素一定比k小。
在原数组中，b数组中的元素位置一定在k之后，也就是说k和这些元素均构成了逆序对。
那么在放入a数组中的元素时，我们通过计算result中b数组的元素个数，就可以计算出对于k来说，b数组中满足逆序对的个数。
又因为递归的过程中，a数组中和k满足逆序对的数也计算过。则在该次递归结束时，[2, 4, 5, 3, 1]中所有k的逆序对个数也就都统计了。
同理对于a中其他的元素也同样有这样的性质。

05	static long num = 0;

06

07	public static void main(String[] args) {

08	Scanner scan = new Scanner(new BufferedInputStream(System.in));

09	while (scan.hasNext()) {

10	int n = scan.nextInt();

11	if (n == 0) {

12

break;

13

}

14

num = 0;

15	int data[] = new int[n];

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

17	data[i] = scan.nextInt();

18

}

19	mergeSort(data, 0, n - 1);

20	System.out.println(num);

21

}

22

}

23

24	static void mergeSort(int[] array, int left, int right) {

25

26	if (left < right) {

27	int center = (left + right) / 2;

28	mergeSort(array, left, center);

29	mergeSort(array, center + 1, right);

30	Merge(array, left, center, right);

31

}

32

}

33

34	static void Merge(int[] array, int left, int center, int right) {

35	//[1,2,3,4] left=1,ceter=2,right=4

36	int[] temp = new int[right - left + 1];

37	int i = left;

38	int j = center + 1;

39	int k = 0;

40	while (i <= center && j <= right) {

41	if (array[i] > array[j]) {

42	temp[k++] = array[j++];

43

44	num += center - i + 1;

45

46

} else {

47	temp[k++] = array[i++];

48

}

49

}

50	while (i <= center) {

51	temp[k++] = array[i++];

52

}

53	while (j <= right) {

54	temp[k++] = array[j++];

55

}

56	for (i = left, k = 0; i <= right; i++, k++) {

57	array[i] = temp[k];

58

}

59

}

http://www.cnblogs.com/frog112111/p/3268632.html
http://www.cnblogs.com/dominatingdashuzhilin/p/4729631.html
分析：由快排的性质很容易发现，只需要求每个数的逆序数累加起来就行了。逆序数可以用树状数组求。
n<500000，0<=a[i]<=999,999,999，很明显数组不可能开这么大，所以需要离散化。
可以用一个结构体
struct node{
int val,pos;
}a[N];
pos表示每个数的下标，val表示该数的值
按val从小到大排序，然后b[a[i].pos]]=i，就实现了离散化，保证了原来序列的大小关系不变。
之后就是简单的树状数组求逆序数了。

      对于第i个数，利用树状数组的结构，将数列中的数逐个插入到树状数组中并统计当前树状数组中在该数之前的数的个数num，i-num即为该数的逆序对数；

      用新数组保存树状数组中数的状态；

 7 int c[N],b[N],n;
 8 struct node{
 9     int val,pos;
10     bool operator <(const node &a)const{
11         return val<a.val;
12     }
13 }a[N];
14 int lowbit(int x)
15 {
16     return x&(-x);
17 }
18 void update(int x,int num)
19 {
20     while(x<=N)
21     {
22         c[x]+=num;
23         x+=lowbit(x);
24     }
25 }
26 LL sum(int x)
27 {
28     LL s=0;
29     while(x>0)
30     {
31         s+=c[x];
32         x-=lowbit(x);
33     }
34     return s;
35 }
36 int main()
37 {
38     int i;
39     while(scanf("%d",&n)&&n)
40     {
41         for(i=1;i<=n;i++)
42         {
43             scanf("%d",&a[i].val);
44             a[i].pos=i;
45         }
46         sort(a+1,a+n+1);
47         for(i=1;i<=n;i++)
48             b[a[i].pos]=i;
49         memset(c,0,sizeof(c));
50         LL ans=0;
51         for(i=1;i<=n;i++)
52         {
53             update(b[i],1);
54             ans+=i-sum(b[i]);
55         }
56         printf("%I64d\n",ans);
57     }
58     return 0;
59 }

http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

3. 离散之后，怎么使用离散后的结果数组来进行树状数组操作，计算出逆序数？

    如果数据不是很大， 可以一个个插入到树状数组中，

    每插入一个数， 统计比他小的数的个数，

    对应的逆序为 i- getsum( aa[i] ),

    其中 i 为当前已经插入的数的个数，

    getsum( aa[i] ）为比 aa[i] 小的数的个数,

    i- sum( aa[i] ) 即比 aa[i] 大的个数， 即逆序的个数