xtu数据结构 C. Ultra-QuickSort

C. Ultra-QuickSort

Time Limit: 7000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

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

解题：求逆序数，归并排序或者快排+树状数组都可以。坑爹的地方在于要使用long long ,害我WA了几次。逗比。。。。。。

树状数组+快速排序

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #define LL long long
13 #define INF 0x3f3f3f
14 using namespace std;
15 const int maxn = 500002;
16 struct node {
17     int val,index;
18 } p[maxn];
19 LL tree[maxn];
20 bool cmp(const node &x,const node &y) {
21     return x.val > y.val;
22 }
23 int lowbit(int x) {
24     return x&(-x);
25 }
26 void update(int x,int val) {
27     for(int i = x; i < maxn; i += lowbit(i)) {
28         tree[i] += val;
29     }
30 }
31 LL sum(int x) {
32     LL ans = 0;
33     for(int i = x; i; i -= lowbit(i)) {
34         ans += tree[i];
35     }
36     return ans;
37 }
38 int main() {
39     int n,i;
40     LL ans;
41     while(scanf("%d",&n),n) {
42         for(i = 0; i < n; i++) {
43             scanf("%d",&p[i].val);
44             p[i].index = i+1;
45         }
46         sort(p,p+n,cmp);
47         memset(tree,0,sizeof(tree));
48         int pre = INT_MIN;
49         for(ans = i = 0; i < n; i++) {
50             update(p[i].index,1);
51             ans += sum(p[i].index-1);
52 
53         }
54         printf("%lld
",ans);
55     }
56     return 0;
57 }

View Code


归并排序

 1 #include <cstdio>
 2 #define LL long long
 3 LL sum,dt[500010];
 4 void mysort(int lft,int rht,int step){
 5     static LL temp[500010];
 6     int md = lft + (step>>1),i = 0,k = 0,j = 0;
 7     while(lft + i < md && md + j < rht){
 8         if(dt[lft+i] > dt[md+j]){temp[k++] = dt[md+j];j++;
 9         }else{temp[k++] = dt[lft+i];i++;sum += j;}
10     }
11     while(lft+i < md){temp[k++] = dt[lft+i];i++;sum += j;}
12     while(md+j < rht){temp[k++] = dt[md+j];j++;}
13     for(i = 0; i < k; i++) dt[lft+i] = temp[i];
14 }
15 void ms(int n){
16     int len = 1,step = 2,m,i,u,v;
17     sum = 0;
18     while(len < n){len <<= 1;}
19     m = len/step;
20     while(step <= len){
21         for(i = 0; i < m; i++){
22             u = i*step;v = (i+1)*step;
23             mysort(u,v>n?n:v,step);
24         }
25         step <<= 1;m = len/step;
26     }
27 }
28 int main(){
29     int n,i;
30     while(scanf("%d",&n),n){
31         for(i = 0; i < n; i++)
32             scanf("%d",dt+i);
33         ms(n);
34         printf("%lld
",sum);
35     }
36     return 0;
37 }

View Code