HDU 1394 역순

#include<iostream>
#include<cstdio>
#define MAXN 11111
using namespace std;

int gt[MAXN<<2],st[MAXN<<2];
int date[MAXN];

void pushUpmax( int rt ){
 	 gt[rt]=max(gt[rt<<1],gt[rt<<1|1]);
}
void pushUpmin( int rt ){
 	 st[rt]=min(st[rt<<1],st[rt<<1|1]);
}

void build( int l,int r,int rt )
{
 	 if( l==r )
 	 {
	  	 gt[rt]=st[rt]=date[l];
	  	 return ;
	 }
	 int m=(l+r)/2;
	 build( l,m,rt<<1 );
	 build( m+1,r,rt<<1|1 );
	 pushUpmax(rt);
	 pushUpmin(rt);
}

int querygt( int v,int l,int r,int rt )//        [l,r]     v    。 
{
 	if( l==r )
 		return 0;
 	if( gt[rt]<v )
 		return r-l+1;
	int m=(l+r)/2;
	int ret=0;
	ret+=querygt( v,l,m,rt<<1 );
	ret+=querygt( v,m+1,r,rt<<1|1 );
	return ret;
}

int queryst( int v,int l,int r,int rt )//        [l,r]     v     
{
 	if( l==r )
 		return 0;
 	if( gt[rt]>v )
 		return r-l+1;
	int m=(l+r)/2;
	int ret=0;
	ret+=queryst( v,l,m,rt<<1 );
	ret+=queryst( v,m+1,r,rt<<1|1 );
	return ret;
}

int main()
{
 	int N;
 	while( scanf("%d",&N)!=EOF )
 	{
	 	   for( int i=1;i<=N;i++ )
	 	   {
		   		scanf( "%d",&date[i] );
		   		date[i+N]=date[i];
		   }
		   build(1,2*N,1);
		   int ans=0;
		   for( int i=1;i<=N;i++ )
		   for( int j=i+1;j<=N;j++ )
		   		if( date[i]>date[j] )
		   			ans++;
		   for( int i=1;i<=N;i++ )
		   		ans=min( ans,ans+queryst(date[i],i+1,i+N-1,1)-querygt(date[i],i+1,i+N-1,1) );
		   
		   printf( "%d
",ans );
  	}
 	return 0;
}

#include<iostream>
using namespace std;

int main()
{
 	int N;
 	while( scanf( "%d",&N )!=EOF )
 	{
	 	   int date[5555],ans=0;
	 	   for( int i=0;i<N;i++ )
	 	   		scanf( "%d",&date[i] );
	 	   for( int i=0;i<N;i++ )
	 	   for( int j=0;j<i;j++ )
	 	   		if( date[j]>date[i] )
	 	   			ans++;
	 	   int temp=ans;
	 	   for( int i=0;i<N;i++ )
	 	   {
		   		temp=temp-date[i]+(N-date[i]-1);
	 	   		ans=min( ans,temp );
		   }
	 	   printf("%d
",ans );
  	}
  	return 0;
}

#include<iostream>
using namespace std;

int tree[5555],N;

void update( int pt,int v )
{
 	 while( pt<=N )
 	 {
	  		tree[pt]+=v;
	  		pt+=pt&(-pt);
	 }
}

int find( int pt )
{
 	int ret=0;
 	while( pt ) 
	{
 	 	   ret+=tree[pt];
 	 	   pt-=pt&(-pt);
    }
 	return ret;
}

int main()
{
 	int date[5555];
 	while( scanf("%d",&N)!=EOF )
 	{
	 	   memset( tree,0,sizeof(tree) );
	 	   for( int i=0;i<N;i++ )
	 	   {
	 	   		scanf( "%d",&date[i] );
	 	   		date[i]++;
		   }
	 	   int ans=0;
		   for( int i=N-1;i>=0;i-- )
	 	   {
		   		ans+=find(date[i]);
		   		update(date[i],1);
		   }
		   printf( "%d
",ans ); 
		   int temp=ans;
		   for( int i=0;i<N;i++ )
		   {
		   		date[i]--;
		   		temp=temp-date[i]+(N-date[i]-1);
		   		ans=min(temp,ans);
   		   }
   		   printf( "%d
",ans );
  	}
  	return 0;
}