●POJ 3378 Crazy Thairs

题链：

题解：

树状数组维护，高精度。

依次考虑以每个位置结尾可以造成的贡献。

假设当前位置为i，为了达到5个元素的要求，我们需要求出，在序列1～i-1中有多少个合法4元组$(a<b<c<d且A_a<A_b<A_c<A_d)$的最后那个元素是小于$A_i$的$(即为了满足a<b<c<d<i且A_a<A_b<A_c<A_d<A_i)$，求出这种四元组的个数，那么就是以i位置结尾可以贡献的答案。

所以我们用树状数组"D4"维护以权值x结尾的合法四元组的个数，那么对于当前的A_i，就只需要查询树状数组的[1~A_i-1]的区间的和，这个和便是应该贡献的答案。

然而为了维护以某一元素结尾的合法四元组的个数，我们不得不再用一个树状数组"D3"维护以权值x结尾的合法三元组的个数。

同理，为了维护以某一元素结尾的合法三元组的个数，还需要一个树状数组"D2"维护以权值x结尾的合法二元组的个数，然后是一个树状数组"D1"维护以权值x结尾的合法一元组的个数。。。。。。

然后就只需要对于依次枚举到的第i个元素，进行查询和更新树状数组就好了。

（本体比较恶心，爆longlong，就再弄一个高精度咯。）

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50050

#define ll long long

using namespace std;

struct BigInt{

	#define Bit 1000

	int val[10],len;

	BigInt(){len=1;memset(val,0,sizeof(val));}

	void operator = (int rtm){

		memset(val,0,sizeof(val));

		len=0; do{

			val[++len]=rtm%Bit; rtm/=Bit;

		}while(rtm);

	}

	BigInt operator + (const BigInt &rtm) const{

		BigInt now; now.len=max(rtm.len,len);

		for(int i=1;i<=now.len;i++){

			now.val[i]+=val[i]+rtm.val[i];

			now.val[i+1]+=now.val[i]/Bit;

			now.val[i]%=Bit;

		}

		while(now.val[now.len+1]) now.len++;

		return now;

	}

	void Print(){

		printf("%d",val[len]);

		for(int i=len-1;i;i--) printf("%03d",val[i]);

	}

};

struct BIT{

	BigInt val[MAXN]; int n;

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

	void Reset(int _n){n=_n; while(_n) val[_n]=0,_n--;}

	void Modify(int p,BigInt v){

		while(p<=n) val[p]=val[p]+v,p+=Lowbit(p);

	}

	BigInt Query(int p){

		static BigInt ret; ret=0;

		while(p)

			ret=ret+val[p],p-=Lowbit(p);

		return ret;

	}

}D1,D2,D3,D4;

int A[MAXN],tmp[MAXN];

int N,tnt;

BigInt ANS,t,one;

int main(){

	one=1;

	while(~scanf("%d",&N)){

		for(int i=1;i<=N;i++)

			scanf("%d",&A[i]),tmp[i]=A[i];

		sort(tmp+1,tmp+N+1);

		tnt=unique(tmp+1,tmp+N+1)-tmp-1;

		for(int i=1;i<=N;i++)

			A[i]=lower_bound(tmp+1,tmp+tnt+1,A[i])-tmp;

		D1.Reset(tnt); D2.Reset(tnt);

		D3.Reset(tnt); D4.Reset(tnt); ANS=0;

		for(int i=1;i<=N;i++){

			D1.Modify(A[i],one); t=D1.Query(A[i]-1);

			D2.Modify(A[i],t); t=D2.Query(A[i]-1);

			D3.Modify(A[i],t); t=D3.Query(A[i]-1);

			D4.Modify(A[i],t);

			t=D4.Query(A[i]-1);

			ANS=ANS+t;

		}

		ANS.Print(); printf("\n");

	}

	return 0;

}