归并求逆序数模板,pku 2299 Ultra-QuickSort,注意long long

#include <stdio.h>
#define MAXN 500000

int height[MAXN+1],temp[MAXN+1];
__int64 sum;

void merge(int *a,int l,int mid,int r) {
    
int i,j,k;
    i
=0,j=l,k=mid;
    
while(j<mid &&<r)    {
        
if(a[j]>a[k]) {
            sum 
+= mid-j;
            temp[i
++= a[k++];
        }

        
else temp[i++= a[j++];
    }

    
while(j<mid)        
        temp[i
++= a[j++];
    
while(k<r)            
        temp[i
++= a[k++];
    
for(i=0; i<r-l; i++) a[l+i] = temp[i];
}

void divide(int *a,int l,int r) {
    
if(l+1<r) {
        
int mid = (l+r)>>1;
        divide(a,l,mid);
        divide(a,mid,r);
        merge(a,l,mid,r);
    }

}


int main() {
    
int n,i;
    
while(scanf("%d",&n)&&n) {
        
for(i=sum=0; i<n; i++) scanf("%d",&height[i]);
        divide(height,
0,n);
        printf(
"%I64d\n",sum);
    }

}
posted on 2008-04-09 12:54 zhongguoa 阅读(512) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理