1.Link：

2.Content：

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 41876		Accepted: 15208

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

59105431230

Sample Output

60

Source

3.Method:

 

4.Code:

1 #include
     
        2 #include
      
         3 using namespace std;  4 int a[500002];  5   6 //递归2路归并排序   7 /*void Merge(long long a[],long long b[],int s,int m,int t)  8 {  9      int i=s,j=m+1,k=s; 10      while((i<=m)&&(j<=t)) 11      { 12          if(a[i]<=a[j]) b[k++]=a[i++];   13          else b[k++]=a[j++]; 14      } 15      while(i<=m) b[k++]=a[i++]; 16      while(j<=t) b[k++]=a[j++]; 17 } 18 void MSort(long long a[],long long b[],int s,int t ,int size) 19 { 20      int m; 21      long long c[size]; 22      if(s==t) b[s]=a[t]; 23      else 24      { 25          m=(s+t)/2; 26          MSort(a,c,s,m,size); 27          MSort(a,c,m+1,t,size); 28          Merge(c,b,s,m,t); 29      } 30 } 31 void MergeSort(long long a[],int size) 32 { 33      MSort(a,a,0,size-1,size); 34 }*/ 35  36  37 // 非递归合并排序 38 /*template
       
         39 void Merge(T a[],T b[],int s,int m,int t) 40 { 41       int i=s,j=m+1,k=s; 42       while(i<=m&&j<=t) 43       { 44          if(a[i]
        
          51 void MergePass(T a[],T b[],int s,int t) 52 { 53       int i; 54       for(i=0;i+2*s<=t;i=i+2*s) 55       { 56         Merge(a,b,i,i+s-1,i+2*s-1); 57      } 58      //剩下的元素个数少于2s 59      if(i+s
         
           63 void MergeSort(T a[],int n) 64 { 65      T *b=new T[n]; 66      //T b[n]; 67      int s=1; 68      while(s
          
           >size)&&size!=0)141 {142 count=0;143 for(i=0;i
          
         
        
       
      
     

 

5.Reference: