POJ 2299 求逆序对（归并排序或树状数组）

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 45290		Accepted: 16440

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

Source

Waterloo local 2005.02.05

归并排序做法：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cstdlib>
 7 #include<string>
 8 using namespace std;
 9 int num[ 500007],num1[500007],num2[5000007];
10 int n;
11 long long ans=0;
12 void get(int left,int mid,int right)
13 {
14     for(int i=left;i<=right;i++)  num1[i]=num[i];
15     int sum=(mid-left)+1;
16     int i=left,j=mid+1,k=left;
17     while(i<=mid&&j<=right){
18         if(num1[i]<=num1[j]){
19             num[k++]=num1[i++];
20         }
21         else
22         {
23           num[k++]=num1[j++];
24           ans+=(mid-i+1);
25         }
26     }
27     while(i<=mid){num[k++]=num1[i++];}
28     while(j<=right){num[k++]=num1[j++];}
29 }
30 
31 void merge1(int l,int r)
32 {
33       if(l<r){
34 
35         int m=(l+r)>>1;
36         merge1(l,m);
37         merge1(m+1,r);
38         get(l,m,r);
39     }
40 }
41 int main()
42 {
43  //  freopen("in.txt","r",stdin);
44     while(1){
45         scanf("%d",&n);
46         ans=0;
47         if(n==0) break;
48         for(int i=0;i<n;i++)
49             scanf("%d",&num[i]);
50         merge1(0,n-1);
51         printf("%I64d
",ans);
52     }
53     return 0;
54 }

树状数组做法：

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define MAX  500010
 8 #define LL long long
 9 using namespace std;
10 int num[MAX],tree[MAX];
11 int n;
12 LL ans=0;
13 struct node
14 {
15     int value,sum;
16 };
17 node arr[MAX];
18 int lowbit(int value)
19 {
20     return value&(-value);
21 }
22 void build(int value)
23 {
24   while(value<=n){
25     tree[value]+=1;
26     value+=lowbit(value);
27   }
28 }
29 int Get_sum(int value)
30 {
31     int result=0;
32   for(int i=value;i>=1;i-=lowbit(i))
33     {
34         result+=tree[i];
35     }
36     return result;
37 }
38 bool cmp(node n1,node n2)
39 {
40     return n1.value<n2.value;
41 }
42 int main()
43 {
44     //freopen("in.txt","r",stdin);
45  while(scanf("%d",&n)==1 && n)
46     {
47         ans=0;
48         memset(tree,0,sizeof(tree));
49         for(int i=1;i<=n;i++) scanf("%d",&arr[i].value),arr[i].sum=i;
50         sort(arr+1,arr+n+1,cmp);
51         for(int i=1;i<=n;i++)
52         {
53             num[arr[i].sum]=i;
54         }
55         for(int i=1;i<=n;i++)
56         {
57             build(num[i]);
58             ans+=i-Get_sum(num[i]);
59         }
60         printf("%I64d
",ans);
61     }
62     return 0;
63 }