pku acm 3378 Crazy Thairs

Crazy Thairs
Time Limit:3000MS  Memory Limit:65536K
Total Submit:1511 Accepted:293

Description

These days, Sempr is crazed on one problem named Crazy Thair. Given N (1 ≤ N ≤ 50000) numbers, which  are no more than 10⁹, Crazy Thair is a group of 5 numbers {i, j, k, l, m} satisfying:

1. 1 ≤ i < j < k < l < m ≤ N
2. A_i < A_j < A_k < A_l < A_m

For example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2, 3, 4, 5, 7}.

Could you help Sempr to count how many Crazy Thairs in the sequence?

Input

Input contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.

Output

Output the amount of Crazy Thairs in each sequence.

Sample Input

5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7

Sample Output

1
4
21

analyze

It is known that we can implement an extended merge sort to evaluate the number of pairs of integer {i, j} (or the number of 2-number groups) satisfying i < j and Ai < Aj. The general idea of this problem is almost the same, which evaluates the number of 3-number groups, 4-number groups and finally 5-number groups step-by-step.
 
code:
//baowp
/*POJ Monthly--2007.09.09
我们知道，在一次归并排序中可以得到形如iAj(逆序数),记录每一个位置长度为2的总数，
再进行一次归并，就可以得到每个位置长度为3的总数(由上一次归并
排序求得)，依此类推，进行到第四次归并排序时就可以求出长度为5
的总数。 
*/
#include 
#define N 50005
typedef struct 
{
	int x;
	int loc;
}Node;
Node a[N];
Node m[N];
__int64 addf[N];
__int64 addc[N];
int t;
void MergeSort(int l,int r)
{
	__int64 sum = 0;

	Node *temp = new Node[r-l+6];
	if( l == r )  return;

	int mid = (l+r)/2;
	MergeSort(l,mid);
	MergeSort(mid+1,r);
	
	int i,j,k;
	i = l , j = mid+1;
	k = 0;

	while( i <= mid && j <= r )
	{
		if( m[i].x < m[j].x )
		{
			temp[k++] = m[i++];
			sum += addf[temp[k-1].loc];
		}
		else 
		{
			temp[k++] = m[j++];
			addc[temp[k-1].loc] += sum;
		}
	}

	while( i <= mid )
		temp[k++] = m[i++];

	while( j <= r )
	{
		temp[k++] = m[j++];
		addc[temp[k-1].loc] += sum;
	}

	k = 0;
	for( i = l ; i <= r ; i++ )
		m[i] = temp[k++];
	delete temp;
}

int main()
{
	int i,j,n;
	while( scanf( "%d" , &n ) != EOF )
	{
		for( i = 1 ; i <= n ; i++ )
		{
			scanf( "%d" , &a[i].x );
			a[i].loc = i;
		}
		if( n < 5 )
		{
			printf( "0\n" );
			continue;
		}
	

		for( i = 1 ; i <= n ; i++ )
			addc[i] = 1;


		int t;
		for( t = 1 ; t < 5 ; t++ )
		{
			for( j = 1 ; j <= n ; j++ )  
			{
				m[j] = a[j];
				addf[j] = addc[j];
				addc[j] = 0;
			}


			MergeSort(1,n);
		}
		__int64 ans1 = 0,ans2 = 0;

		for( i = 1 ; i <= n ; i++ )
		{
			ans1 += (ans2+addc[i])/10000000000000000LL;
			ans2 = (ans2+addc[i])%10000000000000000LL;
		}
		if(ans1)   
		{
			printf( "%I64d" , ans1 );
			printf( "%016I64d\n" , ans2 );
		}
		else
			printf( "%I64d\n", ans2 );

	}
	return 0;
}