Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 50517		Accepted: 18534

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 题解：归并排序注意对dt主数组的更改，由于数据太大999999999所以要离散化 归并：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);typedef long long LL;#define mem(x,y) memset(x,y,sizeof(x))#define T_T while(T--)#define F(i,x) for(i=1;i<=x;i++)#define SI(x) scanf("%d",&x)#define SL(x) scanf("%lld",&x)#define PI(x) printf("%d",x)#define PL(x) printf("%lld",x)#define P_ printf(" ")const int MAXN=500010;int dt[MAXN],b[MAXN];LL ans;void mergesort(int l,int mid,int r){ int ll=l,rr=mid+1,pos=l; while(ll<=mid&&rr<=r){ if(dt[ll]<=dt[rr])b[pos++]=dt[ll++]; else{ ans+=rr-pos; b[pos++]=dt[rr++]; } } for(int i=ll;i<=mid;i++)b[pos++]=dt[i]; for(int i=rr;i<=r;i++)b[pos++]=dt[i]; for(int i=l;i<=r;i++)dt[i]=b[i];}void ms(int l,int r){ if(l
           
            >1; ms(l,mid); ms(mid+1,r); mergesort(l,mid,r); }}int main(){ int N; while(~scanf("%d",&N),N){ int i,j; ans=0; F(i,N) SI(dt[i]); ms(1,N); PL(ans);puts(""); } return 0;}
           
          
         
        
       
      
     

　　离散化树状数组跟归并原理相似；这个是用二分+离散化树状数组写的；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);typedef long long LL;#define mem(x,y) memset(x,y,sizeof(x))#define T_T while(T--)#define F(i,x) for(i=0;i
           
            0){ sm+=tree[x]; x-=lowbit(x); } return sm;}int main(){ int N; while(~scanf("%d",&N),N){ int i,j; mem(tree,0); F(i,N)SI(a[i]),b[i]=a[i]; sort(b,b+N); ans=0; F(i,N){ int pos=lower_bound(b,b+N,a[i])-b; ans+=i-sum(pos); add(pos+1); } PL(ans);puts(""); } return 0;}
           
          
         
        
       
      
     

　　其实用不到二分，结构体就妥了：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);typedef long long LL;#define mem(x,y) memset(x,y,sizeof(x))#define T_T while(T--)#define F(i,x) for(i=0;i
           
            0){ sm+=tree[x]; x-=lowbit(x); } return sm;}int main(){ int N; while(~scanf("%d",&N),N){ int i,j; mem(tree,0); F(i,N)SI(a[i].v),a[i].p=i; sort(a,a+N); ans=0; F(i,N){ ans+=i-sum(a[i].p); add(a[i].p+1); } PL(ans);puts(""); } return 0;}