POJ 3378 Crazy Thairs(ツリー配列最適化)

テーマリンク:http://poj.org/problem?id=3378
数列を与えて、長さが5の上昇サブ列を求めますか?
考え方:まず離散化して、c[i][j]は数字iで終わる長さjのサブ列がいくつあるかを表します.

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <map>





#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)>=0?(x):-(x))

#define i64 long long

#define u32 unsigned int

#define u64 unsigned long long

#define clr(x,y) memset(x,y,sizeof(x))

#define CLR(x) x.clear()

#define ph(x) push(x)

#define pb(x) push_back(x)

#define Len(x) x.length()

#define SZ(x) x.size()

#define PI acos(-1.0)

#define sqr(x) ((x)*(x))

#define MP(x,y) make_pair(x,y)

#define EPS 1e-9



#define FOR0(i,x) for(i=0;i<x;i++)

#define FOR1(i,x) for(i=1;i<=x;i++)

#define FOR(i,a,b) for(i=a;i<=b;i++)

#define FORL0(i,a) for(i=a;i>=0;i--)

#define FORL1(i,a) for(i=a;i>=1;i--)

#define FORL(i,a,b)for(i=a;i>=b;i--)

using namespace std;





void RD(int &x){scanf("%d",&x);}

void RD(u32 &x){scanf("%u",&x);}

void RD(double &x){scanf("%lf",&x);}

void RD(int &x,int &y){scanf("%d%d",&x,&y);}

void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}

void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}

void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}

void RD(int &x,int &y,int &z,int &t){scanf("%d%d%d%d",&x,&y,&z,&t);}

void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}

void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}

void RD(char &x){x=getchar();}

void RD(char *s){scanf("%s",s);}

void RD(string &s){cin>>s;}





void PR(int x) {printf("%d
",x);}

void PR(int x,int y) {printf("%d %d
",x,y);}

void PR(i64 x) {printf("%lld
",x);}

void PR(u32 x) {printf("%u
",x);}

void PR(double x) {printf("%.5lf
",x);}

void PR(char x) {printf("%c
",x);}

void PR(char *x) {printf("%s
",x);}

void PR(string x) {cout<<x<<endl;}





const i64 MOD=10000000;

class BigNum

{

public:

    int a[10];



    BigNum operator+(BigNum temp)

    {

        BigNum ans;

        int i,j,k,p;

        if(a[0]>temp.a[0]) p=a[0];

        else p=temp.a[0];

        for(i=a[0],j=temp.a[0],k=p;j>=1&&i>=1;i--,j--,k--)

        {

            ans.a[k]=a[i]+temp.a[j];

        }

        if(j==0)

        {

            while(i>=1) ans.a[i]=a[i--];

        }

        else

        {

            while(j>=1) ans.a[j]=temp.a[j--];

        }

        ans.a[0]=0;

        for(i=p;i>=1;i--)

        {

            ans.a[i-1]+=ans.a[i]/MOD;

            ans.a[i]%=MOD;

        }

        if(ans.a[0])

        {

            for(i=p+1;i>=1;i--) ans.a[i]=ans.a[i-1];

            ans.a[0]=p+1;

        }

        else ans.a[0]=p;

        return ans;

    }



    BigNum()

    {

        a[0]=1;

        a[1]=0;

    }



    BigNum(int x)

    {

        if(x>=MOD) a[0]=2,a[1]=x/MOD,a[2]=x%MOD;

        else a[0]=1,a[1]=x;

    }



    void print()

    {

        int i=1;

        while(i<=a[0]&&a[i]==0) i++;

        if(i>a[0])

        {

            puts("0");

            return;

        }

        printf("%d",a[i++]);

        while(i<=a[0]) printf("%07d",a[i++]);

    }

};





const int N=50005;

int a[N],b[N];

BigNum c[N][6];

int n,M;





int find(int low,int high,int x)

{

    int mid;

    while(low<=high)

    {

        mid=(low+high)>>1;

        if(b[mid]==x) return mid;

        if(b[mid]>x) high=mid-1;

        else low=mid+1;

    }

}





BigNum get(int x,int t)

{

    BigNum ans=BigNum(0);

    while(x>0)

    {

        ans=ans+c[x][t];

        x-=x&-x;

    }

    return ans;

}





void update(int x,int t,BigNum temp)

{

    while(x<M)

    {

        c[x][t]=c[x][t]+temp;

        x+=x&-x;

    }

}



int main()

{

    while(scanf("%d",&n)!=-1)

    {

        int i,j;

        FOR0(i,n) RD(a[i]),b[i]=a[i];

        sort(b,b+n);

        int x=unique(b,b+n)-b;

        FOR0(i,n) a[i]=find(0,x-1,a[i])+1;

        FOR1(i,M) FOR0(j,6) c[i][j]=BigNum(0);

        M=x+2;

        BigNum temp,ans=BigNum(0);

        FOR0(i,n)

        {

            FORL1(j,4)

            {

                temp=get(a[i]-1,j);

                update(a[i],j+1,temp);

            }

            update(a[i],1,BigNum(1));

        }

        temp=get(M-1,5);

        temp.print();

        puts("");

    }

    return 0;

}