poj--2299 Ultra-QuickSort（树状数组求逆序数）

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

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

Sample Output

6
0

题意：给出一个数组，只能够相邻的两个数进行交换求最少有多少次操作后能变成由小到大排列。

思路：这个题是求逆序数可用树状数组求逆序数或者用归并排序求逆序数。

树状数组AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 int c[500005],n;
 7 struct note
 8 {
 9     int x,y;
10 } a[500005];
11 int cmp(const struct note &a,const struct note &b)
12 {
13     return a.x<b.x;
14 }
15 int lowbit(int m)
16 {
17     return m&(-m);
18 }
19 int updata(int p,int q)
20 {
21     while(p<=n)
22     {
23         c[p]+=q;
24         p+=lowbit(p);
25     }
26     return 0;
27 }
28 int getsum(int m)
29 {
30     int sum;
31     sum=0;
32     while(m)
33     {
34         sum+=c[m];
35         m-=lowbit(m);
36     }
37     return sum;
38 }
39 int main()
40 {
41     long long ans;
42     while(~scanf("%d",&n))
43     {
44         if(n==0)
45             break;
46         memset(c,0,sizeof(c));
47         for(int i=1; i<=n; i++)
48         {
49             scanf("%d",&a[i].x);
50             a[i].y=i;
51         }
52         sort(a+1,a+n+1,cmp);
53         ans=0;
54         for(int i=1; i<=n; i++)
55         {
56             updata(a[i].y,1);
57             ans+=i-getsum(a[i].y);
58         }
59         printf("%lld
",ans);
60     }
61     return 0;
62 }

View Code

归并排序AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 int a[500005],c[500005];
 7 long long cnt;
 8 void mergesort(int l,int r)
 9 {
10     int mid,i,j,tmp;
11     if(r>l+1)
12     {
13         mid=(l+r)/2;
14         mergesort(l,mid);
15         mergesort(mid,r);
16         tmp=l;
17         for(i=l,j=mid; i<mid&&j<r;)
18         {
19             if(a[i]>a[j])
20             {
21                 c[tmp++]=a[j++];
22                 cnt+=mid-i;
23             }
24             else
25                 c[tmp++]=a[i++];
26         }
27         if(j<r)
28             for(; j<r; ++j)
29                 c[tmp++]=a[j];
30         else
31             for(; i<mid; ++i)
32                 c[tmp++]=a[i];
33         for(i=l; i<r; ++i)
34             a[i]=c[i];
35     }
36 }
37 int main()
38 {
39     int n;
40     while(~scanf("%d",&n))
41     {
42         if(n==0)
43             break;
44         memset(c,0,sizeof(c));
45         for(int i=0; i<n; i++)
46             scanf("%d",&a[i]);
47         cnt=0;
48         mergesort(0,n);
49         printf("%lld
",cnt);
50     }
51     return 0;
52 }

View Code

提示：由于数据较大，答案应该用 long long储存。