随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 3378 Crazy Thairs

题目链接:http://poj.org/problem?id=3378
/*
题意:
    给定N (1 <= N <= 50000) 个小于等于10^9的数Ai, 要求找出Crazy Thair的数量。
Crazy Thair是一个五元组{i, j, k, l, m}满足: 
1. 1 <= i < j < k < l < m <= N
2. Ai < Aj < Ak < Al < Am 

解法:
    树状数组

思路:
    可以参考以下这题的解法:
http://www.cppblog.com/menjitianya/archive/2011/04/06/143510.html
    那一题求得是非递减数列的数量,没有要求元素个数,这题是要求元素个数一定要
是5个,我们还是可以写出状态转移方程:
dp[i][j] = sum{ dp[i-1][k], k<j, a[k] < a[j] } dp[i][j]表示长度为i以j结尾的
序列的数量,这题需要建立5个树状数组,sum这一步操作就可以通过树状数组的成段求
和来做。每次求i-1的满足情况的解,完毕后就将答案插入到i的树状数组中。
    当长度为5的时候就是最后的答案了,累加即可。
*/

#include 
<iostream>
#include 
<algorithm>
using namespace std;

typedef 
int hugeint;
const int Base = 10000
const int Capacity = 7;

struct xnum {
    
int Len;
    
int Data[Capacity];
    xnum() : Len(
0{}
    xnum(
const xnum& V) : Len(V.Len) {
        memcpy(Data, V.Data, Len 
* sizeof *Data);
    }

    xnum(
int V) : Len(0
        
for (; V > 0; V /= Base) Data[Len++= V % Base;
    }

    xnum(
char S[]);
    xnum
& operator=(const xnum& V) 
        Len 
= V.Len;
        memcpy(Data, V.Data, Len 
* sizeof *Data); 
        
return *this;
    }

    
int& operator[](int Index) return Data[Index]; }
    
int operator[](int Index) const return Data[Index]; }
    
void print(){
        printf(
"%d",Len==0?0:Data[Len-1]);
        
for(int i=Len-2;i>=0;i--)
            
for(int j=Base/10;j>0;j/=10)
                printf(
"%d",Data[i]/j%10);
    }

}
;

xnum::xnum(
char S[]) {
    
int I, J;
    Data[Len 
= 0= 0;
    J 
= 1;
    
for (I = strlen(S)-1; I>=0; I--{
        Data[Len] 
+= (S[I] - '0'* J;
        J 
*= 10;
        
if (J >= Base) J = 1, Data[++Len] = 0;
    }

    
if (Data[Len] > 0) Len++;
}


int compare(const xnum& A, const xnum& B) {
    
int I;
    
if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1;
    
for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--);
    
if (I < 0return 0;
    
return A[I] > B[I] ? 1 : -1;
}


xnum 
operator+(const xnum& A, const xnum& B) {
    xnum R;
    
int I;
    
int Carry = 0;
    
for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++)
    
{
        
if (I < A.Len) Carry += A[I];
        
if (I < B.Len) Carry += B[I];
        R[I] 
= Carry % Base;
        Carry 
/= Base;
    }

    R.Len 
= I;
    
return R;
}


xnum 
operator-(const xnum& A, const xnum& B) {
    xnum R;
    
int Carry = 0;
    R.Len 
= A.Len;
    
int I;
    
for (I = 0; I < R.Len; I++{
        R[I] 
= A[I] - Carry;
        
if (I < B.Len) R[I] -= B[I];
        
if (R[I] < 0) Carry = 1, R[I] += Base;
        
else Carry = 0;
    }

    
while (R.Len > 0 && R[R.Len - 1== 0) R.Len--;
    
return R;
}


xnum 
operator*(const xnum& A, const int B) {
    
int I;
    
if (B == 0return 0;
    xnum R;
    hugeint Carry 
= 0;
    
for (I = 0; I < A.Len || Carry > 0; I++)
    
{
        
if (I < A.Len) Carry += hugeint(A[I]) * B;
        R[I] 
= Carry % Base;
        Carry 
/= Base;
    }

    R.Len 
= I;
    
return R;
}


xnum 
operator*(const xnum& A, const xnum& B) {
    
int I;
    
if (B.Len == 0return 0;
    xnum R;
    
for (I = 0; I < A.Len; I++{
        hugeint Carry 
= 0;
        
for (int J = 0; J < B.Len || Carry > 0; J++{
            
if (J < B.Len) Carry += hugeint(A[I]) * B[J];
            
if (I + J < R.Len) Carry += R[I + J];
            
if (I + J >= R.Len) R[R.Len++= Carry % Base;
            
else R[I + J] = Carry % Base;
            Carry 
/= Base;
        }
   
    }

    
return R;
}


xnum 
operator/(const xnum& A, const int B) {
    xnum R;
    
int I;
    hugeint C 
= 0;
    
for (I = A.Len - 1; I >= 0; I--)
    
{
        C 
= C * Base + A[I];
        R[I] 
= C / B;
        C 
%= B;
    }

    R.Len 
= A.Len;
    
while (R.Len > 0 && R[R.Len - 1== 0) R.Len--;
    
return R;
}


xnum 
operator/(const xnum& A, const xnum& B) {
    
int I;
    xnum R, Carry 
= 0;
    
int Left, Right, Mid;
    
for (I = A.Len - 1; I >= 0; I--{
        Carry 
= Carry * Base + A[I];
        Left 
= 0;
        Right 
= Base - 1;
        
while (Left < Right) {
            Mid 
= (Left + Right + 1/ 2;
            
if (compare(B * Mid, Carry) <= 0) Left = Mid;
            
else Right = Mid - 1;
        }

        R[I] 
= Left;
        Carry 
= Carry - B * Left;
    }

    R.Len 
= A.Len;
    
while (R.Len > 0 && R[R.Len - 1== 0) R.Len--;
    
return R;
}


xnum 
operator%(const xnum& A, const xnum& B) {
    
int I;
    xnum R, Carry 
= 0;
    
int Left, Right, Mid;
    
for (I = A.Len - 1; I >= 0; I--{
        Carry 
= Carry * Base + A[I];
        Left 
= 0;
        Right 
= Base - 1;
        
while (Left < Right) {
            Mid 
= (Left + Right + 1/ 2;
            
if (compare(B * Mid, Carry) <= 0) Left = Mid;
            
else Right = Mid - 1;
        }

        R[I] 
= Left;
        Carry 
= Carry - B * Left;
    }

    R.Len 
= A.Len;
    
while (R.Len > 0 && R[R.Len - 1== 0) R.Len--;
    
return Carry;
}


istream
& operator>>(istream& In, xnum& V) {
    
char Ch;
    
for (V = 0; In >> Ch;) {
        V 
= V * 10 + (Ch - '0');
        
if (cin.peek() <= ' 'break;
    }

    
return In;
}


ostream
& operator<<(ostream& Out, const xnum& V) {
    
int I;
    Out 
<< (V.Len == 0 ? 0 : V[V.Len - 1]);
    
for (I = V.Len - 2; I >= 0; I--
        
for (int J = Base / 10; J > 0; J /= 10
            Out 
<< V[I] / J % 10;
        
return Out;
}


xnum gcd(xnum a,xnum b) 
{
    
if(compare(b,0)==0return a;
    
else return gcd(b,a%b); 
}


int div(char *A,int B) {
    
int I;
    
int C = 0;
    
int Alen=strlen(A);
    
for (I = 0; I <Alen; I++)
    
{
        C 
= C * Base + A[I]-'0';
        C 
%= B;
    }

    
return C;
}


#define maxn 50010

int n;
xnum c[
6][maxn];
int val[maxn], bin[maxn], tot;

int lowbit(int x) {
    
return x & (-x);
}


void add(int idx, int pos, xnum v) {
    
while(pos <= n) {
        c[idx][pos] 
= c[idx][pos] + v;
        pos 
+= lowbit(pos);
    }

}


xnum sum(
int idx, int pos) {
    xnum s 
= 0;
    
while(pos > 0{
        s 
= s + c[idx][pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}


int Bin(int v) {
    
int l = 1;
    
int r = tot;
    
while(l <= r) {
        
int m = (l + r) >> 1;
        
if(bin[m] == v)
            
return m;
        
if(v > bin[m]) {
            l 
= m + 1;
        }
else
            r 
= m - 1;
    }

}



int main() {
    
int i, j;
    
while(scanf("%d"&n) != EOF) {
        tot 
= 0;
        
for(i = 1; i <= n; i++{
            scanf(
"%d"&val[i]);
            bin[i] 
= val[i];
        }

        sort(bin
+1, bin+1+n);
        
for(i = 1; i <= n; i++{
            
if(i==1 || bin[i] != bin[i-1])
                bin[ 
++tot ] = bin[i];
        }

        
for(i = 0; i <= 5; i++{
            
for(j = 1; j <= n; j++)
                c[i][j] 
= 0;
        }


        
for(i = 1; i <= n; i++{
            val[i] 
= Bin(val[i]);
        }

        xnum ans 
= 0;
        
for(i = 1; i <= n; i++{
            add(
1, val[i], 1);
            
for(j = 2; j <= 5; j++{
                xnum p 
= sum(j-1, val[i]-1);
                
if(p.Len)
                    add(j, val[i], p);

                
if(j == 5{
                    ans 
= ans + p;
                }

            }

        }

        ans.print();
        puts(
"");
    }

    
return 0;
}

posted on 2011-04-07 13:16 英雄哪里出来 阅读(1480) 评论(0)  编辑 收藏 引用 所属分类: 树状数组


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理