poj 2299 UltraQuickSort

题目：http://poj.org/problem?id=2299

一开始敲了一个冒泡，但是一看数据范围很大，会超时，然后想了想也没想出来什么好的方法，搜了一下解题报告，是逆序数的问题，线代学的不好，都忘了，搜了一下，用的是归并，还有一个方法是树状数组，没接触过树状数组，所以有了解了一下树状数组

归并：

在合并的过程中是将两个相邻并且有序的序列合并成一个有序序列，如以下两个有序序列

Seq1：3 4 5

Seq2：2 6 8 9

合并成一个有序序:

Seq：2 3 4 5 6 8 9

对于序列seq1中的某个数a[i],序列seq2中的某个数a[j]，如果a[i]<a[j],没有逆序数，如果a[i]>a[j]，那么逆序数为seq1中a[i]后边元素的个数(包括a[i])，即len1-i+1,

这样累加每次递归过程的逆序数，在完成整个递归过程之后，最后的累加和就是逆序的总数

注：要用__int64，long和long long会wa

代码：

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 __int64 a[500010];
 5 __int64 b[500010];
 6 __int64 merge(int low,int mid,int high)
 7 {
 8     int i=low,j=mid+1;
 9     int k=0;
10     __int64 num=0;
11     while(i<=mid&&j<=high)
12     {
13         if(a[i]<=a[j])
14         b[k++]=a[i++];
15         else
16         {
17             b[k++]=a[j++];
18             num+=mid-i+1;
19         }
20     }
21     while(i<=mid)
22     {
23         b[k++]=a[i++];
24     }
25     while(j<=high)
26     {
27         b[k++]=a[j++];
28     }
29     k=0;
30     for(i=low;i<=high;i++)
31     {
32         a[i]=b[k];
33         k++;
34     }
35     return num;
36 }
37 __int64 mergesort(int a,int b)
38 {
39     if(a<b)
40     {
41         int mid;
42         __int64 count=0;
43         mid=(a+b)/2;
44         count+=mergesort(a,mid);
45         count+=mergesort(mid+1,b);
46         count+=merge(a,mid,b);
47         return count;
48     }
49     return 0;
50 }
51 
52 int main()
53 {
54     int n,i;
55     while(scanf("%d",&n)!=EOF)
56     {
57         if(n==0)
58         break;
59         for(i=0;i<n;i++)
60         {
61             scanf("%I64d",&a[i]);
62         }
63 
64         printf("%I64d\n",mergesort(0,n-1));
65     }
66     return 0;
67 }

树状数组：

序列：

3 5 4 8 2 6 9

先将原序列从大到小排序；

初始化一个数组

0 0 0 0 0 0 0

将最大的元素的位置变为1

0 0 0 0 0 0 1

然后放第二大的元素

0 0 0 1 0 0 1

。。。。。

依次进行下去，每次统计在该位置之前的放的元素的个数，然后相加，就是逆序数的总数。

统计每个位置之前的元素的个数的时候可以用树状数组实现

代码：

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 struct node
 7 {
 8     __int64 data;
 9     __int64 pos;
10 }su[500010];
11 int tree[500010];
12 __int64 num;
13 __int64 n;
14 
15 __int64 lowbit(__int64 num)
16 {
17     return num&(num^(num-1));
18 }
19 
20 __int64 sum(__int64 pos)
21 {
22     __int64 ans=0;
23     while(pos>0)
24     {
25         ans+=tree[pos];
26         pos-=lowbit(pos);
27     }
28     return ans;
29 }
30 void update(__int64 pos)
31 {
32     while(pos<=n)
33     {
34         tree[pos]++;
35         pos+=lowbit(pos);
36     }
37 }
38 bool cmp(node a,node b)
39 {
40     return a.data>b.data;
41 }
42 int main()
43 {
44 
45     while(scanf("%I64d",&n)!=EOF)
46     {
47         if(n==0)
48         break;
49         int i;
50         for(i=1;i<=n;i++)
51         {
52             scanf("%I64d",&su[i].data);
53             su[i].pos=i;
54         }
55         sort(su+1,su+n+1,cmp);
56         num=0;
57         memset(tree,0,sizeof(tree));
58         for(i=1;i<=n;i++)
59         {
60             num+=sum(su[i].pos);
61             update(su[i].pos);
62         }
63         printf("%I64d\n",num);
64     }
65     return 0;
66 }