首页 > 专题系列 > Java解POJ > POJ 3378 Crazy Thairs [解题报告] Java
2013
11-12

POJ 3378 Crazy Thairs [解题报告] Java

Crazy Thairs

问题描述 :

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

1. 1 ≤ i < j < k < l < m N
2. Ai < Aj < Ak < Al < Am

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 contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.

输出:

Output the amount of Crazy Thairs in each sequence.

样例输入:

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

样例输出:

1
4
21

解题代码:

//* @author: ccQ.SuperSupper
import java.util.*;
import java.math.*;

class Binary
{
	int n,i;
	long ret;
	long a[],c[];
	void init(int x)
	{
		n = x;
		a = new long [x+10];
		c = new long [x+10];
		for(i=0;i< x+10;++i)
		{
			a[i]=c[i]=0;
		}
	}
	void update(int x,long v)
	{
		a[x]+=v;
		for(i=x;i<=n;i+=lowbit(i)) c[i]+=v;
	}
	int lowbit(int x)
	{
		return (x)&(-x);
	}
	long query(int x)
	{
		for(ret=0,i=x;i>0;i^=lowbit(i)) ret+=c[i];
		return ret;
	}
}
public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
	// TODO Auto-generated method stub
	int n,i,j;
	int way[] = new int[50010];
	int num[] = new int[50010];
	int mapping[]= new int[50010];
	
	BigInteger ans,temp;
		
	Binary array[] = new Binary[5];
	
     Scanner cin = new Scanner(System.in);
     while(cin.hasNext())
     {
	n = cin.nextInt();
	for(i=0;i< n;++i)
	{
		way[i]=cin.nextInt();
		num[i]=way[i];
	}
	Arrays.sort(num,0,n);
	mapping[0]=2;
	for(i=1;i< n;++i)
	{
		if(num[i]==num[i-1]) mapping[i]=mapping[i-1];
		else mapping[i]=mapping[i-1]+1;
	}
		
	for(i=0;i< n;++i)
	{
		way[i]=mapping[binary_search(0,n-1,way[i],num)];
	}
	for(i=0;i< 5;++i)
	{
		array[i]=new Binary();
		array[i].init(50010);
	}
			
	ans = new BigInteger("0");
	for(i=0;i< n;++i)
	{
		for(j=4;j>0;--j)
		{
		   array[j].update(way[i], array[j-1].query(way[i]-1));
		}
		array[1].update(way[i], 1);
				
		temp = BigInteger.valueOf(array[4].query(way[i]-1));
		ans = ans.add(temp);
	}
			
	System.out.println(ans);
			
	}
 }
	public static int binary_search(int left,int right,int value,int num[])
	{
		int mid;
		while(left+1< right)
		{
			mid=(left+right)/2;
			if(num[mid]>value) right = mid;
			else left = mid;
		}
		if(num[left]==value) return left;
		return right;
	}

}