|
题目链接:http://poj.org/problem?id=3378
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给定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/Images/OutliningIndicators/InBlock.gif)
解法:
树状数组
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
可以参考以下这题的解法:
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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef int hugeint;
const int Base = 10000;
const int Capacity = 7;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct xnum {
int Len;
int Data[Capacity];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) xnum() : Len(0) {}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) xnum(const xnum& V) : Len(V.Len) {
memcpy(Data, V.Data, Len * sizeof *Data);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) xnum(int V) : Len(0) {
for (; V > 0; V /= Base) Data[Len++] = V % Base;
}
xnum(char S[]);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) xnum& operator=(const xnum& V) {
Len = V.Len;
memcpy(Data, V.Data, Len * sizeof *Data);
return *this;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) int& operator[](int Index) { return Data[Index]; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) int operator[](int Index) const { return Data[Index]; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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);
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum::xnum(char S[]) {
int I, J;
Data[Len = 0] = 0;
J = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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 < 0) return 0;
return A[I] > B[I] ? 1 : -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator-(const xnum& A, const xnum& B) {
xnum R;
int Carry = 0;
R.Len = A.Len;
int I;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator*(const xnum& A, const int B) {
int I;
if (B == 0) return 0;
xnum R;
hugeint Carry = 0;
for (I = 0; I < A.Len || Carry > 0; I++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if (I < A.Len) Carry += hugeint(A[I]) * B;
R[I] = Carry % Base;
Carry /= Base;
}
R.Len = I;
return R;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator*(const xnum& A, const xnum& B) {
int I;
if (B.Len == 0) return 0;
xnum R;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (I = 0; I < A.Len; I++) {
hugeint Carry = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator/(const xnum& A, const int B) {
xnum R;
int I;
hugeint C = 0;
for (I = A.Len - 1; I >= 0; I--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator/(const xnum& A, const xnum& B) {
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (I = A.Len - 1; I >= 0; I--) {
Carry = Carry * Base + A[I];
Left = 0;
Right = Base - 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum operator%(const xnum& A, const xnum& B) {
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (I = A.Len - 1; I >= 0; I--) {
Carry = Carry * Base + A[I];
Left = 0;
Right = Base - 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) istream& operator>>(istream& In, xnum& V) {
char Ch;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (V = 0; In >> Ch;) {
V = V * 10 + (Ch - '0');
if (cin.peek() <= ' ') break;
}
return In;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum gcd(xnum a,xnum b) {
if(compare(b,0)==0) return a;
else return gcd(b,a%b);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int div(char *A,int B) {
int I;
int C = 0;
int Alen=strlen(A);
for (I = 0; I <Alen; I++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
C = C * Base + A[I]-'0';
C %= B;
}
return C;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 50010
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
xnum c[6][maxn];
int val[maxn], bin[maxn], tot;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int x) {
return x & (-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void add(int idx, int pos, xnum v) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos <= n) {
c[idx][pos] = c[idx][pos] + v;
pos += lowbit(pos);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) xnum sum(int idx, int pos) {
xnum s = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos > 0) {
s = s + c[idx][pos];
pos -= lowbit(pos);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Bin(int v) {
int l = 1;
int r = tot;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == v)
return m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(v > bin[m]) {
l = m + 1;
}else
r = m - 1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d", &n) != EOF) {
tot = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
bin[i] = val[i];
}
sort(bin+1, bin+1+n);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
if(i==1 || bin[i] != bin[i-1])
bin[ ++tot ] = bin[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i <= 5; i++) {
for(j = 1; j <= n; j++)
c[i][j] = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
val[i] = Bin(val[i]);
}
xnum ans = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
add(1, val[i], 1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(j = 2; j <= 5; j++) {
xnum p = sum(j-1, val[i]-1);
if(p.Len)
add(j, val[i], p);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(j == 5) {
ans = ans + p;
}
}
}
ans.print();
puts("");
}
return 0;
}
|