항 저 우 전기 hdu 1394 최소 Inversion Number[선분 수+상세 주석+난이도 있 음]

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1394
    Name  : 1394 Minimum Inversion Number

    Date  : Saturday, September 17, 2011
    Time Stage : 4 hours

    Result: 
4618941	2011-09-17 18:27:45	Accepted	1394
62MS	280K	2745 B
C++	pyy

4618908	2011-09-17 18:22:09	Accepted	1394
62MS	280K	2707 B
C++	pyy

4618903	2011-09-17 18:21:09	Compilation Error
1394
0MS	0K	1662 B
C++	pyy


Test Data :

Review :
 ，   ，       。      ，       ，
       ，       ，      ，      
    “   ”         ，           
    ……

                ，           ， 
   ，         ，                ，
      ……
//----------------------------------------------------------------------------*/

#include 
#include 

int max (int lhs, int rhs)
{
	return (lhs > rhs ? lhs : rhs) ;
}

int min (int lhs, int rhs)
{
	return lhs < rhs ? lhs : rhs ;
}

typedef struct {
	int left, right ;
	int sum ;
} NODE ;

#define MAXSIZE 5001

int n ;
int a[MAXSIZE] ;
NODE segTree[MAXSIZE * 2] ;

//      
void build (int id, int left, int right)
{
	segTree[id].left	= left ;
	segTree[id].right	= right ;
	segTree[id].sum = 0 ;

	if (left == right)
		return ;
	
	int mid = (left + right) / 2 ;
	build (id * 2, left, mid) ;
	build (id * 2 + 1, mid + 1, right) ;
}

int query (int id, int left, int right)
{
	//                   (left, right)     
	if (segTree[id].left > right || segTree[id].right < left)
		return 0 ;
	//                    
	if (left == segTree[id].left && segTree[id].right == right)
		return segTree[id].sum ;

	int mid = (segTree[id].left + segTree[id].right) / 2 ;
	int sum = 0 ;

	if (right < mid)			//               
		sum += query (id * 2, left, right) ;
	//               ,     hdu      ，
	//         mid < left    ……
	else if (mid + 1 < left)
		sum += query (id * 2 + 1, left, right) ;
	else						//                 
		sum += query (id * 2, left, mid) + query (id * 2 + 1, mid + 1, right) ;

	return sum ;
}

int update (int id, int val)
{
	//     
	if (segTree[id].left == val && segTree[id].right == val)
	{
		return segTree[id].sum = 1 ;
	}

	// val              
	if (segTree[id].left > val || segTree[id].right < val)
		return 0 ;

	int mid = (segTree[id].left + segTree[id].right) / 2 ;

	// val            
	if (mid < val)	//     
		segTree[id].sum += update (id * 2 + 1, val) ;
	// val            
	else
		segTree[id].sum += update (id * 2, val) ;

	return 1 ;
}

int main ()
{
	int i, j ;
	int sum, res ;
	while (scanf ("%d", &n) != EOF)
	{
		//      
		build (1, 1, n) ;
		sum = 0 ;
		for (i = 0 ; i < n ; ++i)
		{
			scanf ("%d", &a[i]) ;
			//     a[i]         ，       ，
			//       x > a[i]      
			sum += query (1, a[i] + 1, n - 1) ;
			//      ，  a[i]       
			update (1, a[i]) ;
		}

		//           ：         ，        a 
		//    a     a        a  ：0, 1, 2, ... , a - 1
		res = sum ;
		for (i = 0 ; i < n ; ++i)
		{
			sum = sum - a[i] + (n - a[i] - 1) ;
			res = min (res, sum) ;
		}
		printf ("%d
", res) ;
	}
	return 0 ;
}