#include<iostream>
using namespace std;
#define MAXN 500000
int x[MAXN+1];
int z[MAXN+1];
__int64 reverse;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void merge(int low,int mid,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i=low,j=mid+1,q=0;
while (i<=mid && j<=high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (x[i]<=x[j])
z[q++]=x[i++];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
z[q++]=x[j++];
reverse+=mid-i+1;
}
}
while (i<=mid)
z[q++]=x[i++];
while (j<=high)
z[q++]=x[j++];
for(i=0;i<q;i++)
x[low+i]=z[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void mergesort(int low,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int mid;
if ( low< high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,i;
while(scanf("%d",&n)==1 && n!=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=0;i<n;i++)
scanf("%d",&x[i]);
reverse=0;
mergesort(0,n-1);
printf("%I64d\n",reverse);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}
posted on 2009-07-12 14:59
wyiu 阅读(90)
评论(0) 编辑 收藏 引用 所属分类:
POJ