Poj Solution 3378

http://poj.org/problem?id=3378

//* @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;
    }

}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *