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了几次。逗比。。。。。。

树状数组+快速排序

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 const int maxn = ;

 struct node {

     int val,index;

 } p[maxn];

 LL tree[maxn];

 bool cmp(const node &x,const node &y) {

     return x.val > y.val;

 }

 int lowbit(int x) {

     return x&(-x);

 }

 void update(int x,int val) {

     for(int i = x; i < maxn; i += lowbit(i)) {

         tree[i] += val;

     }

 }

 LL sum(int x) {

     LL ans = ;

     for(int i = x; i; i -= lowbit(i)) {

         ans += tree[i];

     }

     return ans;

 }

 int main() {

     int n,i;

     LL ans;

     while(scanf("%d",&n),n) {

         for(i = ; i < n; i++) {

             scanf("%d",&p[i].val);

             p[i].index = i+;

         }

         sort(p,p+n,cmp);

         memset(tree,,sizeof(tree));

         int pre = INT_MIN;

         for(ans = i = ; i < n; i++) {

             update(p[i].index,);

             ans += sum(p[i].index-);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

归并排序

 #include <cstdio>

 #define LL long long

 LL sum,dt[];

 void mysort(int lft,int rht,int step){

     static LL temp[];

     int md = lft + (step>>),i = ,k = ,j = ;

     while(lft + i < md && md + j < rht){

         if(dt[lft+i] > dt[md+j]){temp[k++] = dt[md+j];j++;

         }else{temp[k++] = dt[lft+i];i++;sum += j;}

     }

     while(lft+i < md){temp[k++] = dt[lft+i];i++;sum += j;}

     while(md+j < rht){temp[k++] = dt[md+j];j++;}

     for(i = ; i < k; i++) dt[lft+i] = temp[i];

 }

 void ms(int n){

     int len = ,step = ,m,i,u,v;

     sum = ;

     while(len < n){len <<= ;}

     m = len/step;

     while(step <= len){

         for(i = ; i < m; i++){

             u = i*step;v = (i+)*step;

             mysort(u,v>n?n:v,step);

         }

         step <<= ;m = len/step;

     }

 }

 int main(){

     int n,i;

     while(scanf("%d",&n),n){

         for(i = ; i < n; i++)

             scanf("%d",dt+i);

         ms(n);

         printf("%lld\n",sum);

     }

     return ;

 }

巴特西