1028_mergesort.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cassert>
using namespace std;

const int MAXN = 15000 ;
struct node { int x, no; } a[ MAXN+1 ];
int lev[ MAXN+1 ];
int n;

void readin()
{
	scanf("%d",&n);
	for( int i=1; i<=n; ++i )
	{
		scanf("%d%*d",&a[i].x);
		a[i].no = i ;
	}
}

void merge( int c, int d )
{
	if( c==d ) return ;
	static node ta[ MAXN+1 ];
	
	int mid = (c+d)>>1 ;
	merge( c, mid ) , merge( mid+1, d );
	
	for( int i=c, j=mid+1, p=c;  p<=d; )
		if( i<=mid && ( j>d || a[i].x <= a[j].x ) ) //!! be careful !!
			ta[p++] = a[i++] ; 
		else
		{
			lev[ a[j].no ] += i-c ;
			ta[p++] = a[j++] ;
		}
		
	memcpy( a+c, ta+c, sizeof(ta[0])*(d-c+1) );
}

void outans()
{
	static int ans[ MAXN ];
	memset( ans, 0, sizeof(ans[0])*n );
	
	int i;
	for( i=1; i<=n; ++i ) ++ ans[ lev[i] ] ;
	for( i=0; i< n; ++i ) printf("%d\n",ans[i]);
}

int main()
{
	readin();
	
	memset( lev, 0, sizeof(lev[0])*(n+1) );
	merge( 1, n );
	
	outans();
	
	system("pause");
	return 0;
}