PKU 3378 Crazy Thairs

問題:

3378 -- Crazy Thairs

問題概要:

長さNの数列aが与えられる。i < j < k < l < m かつ、a_i < a_j < a_k < a_l < a_mであるような要素の組は何個ありますかという問題。

同じ値が2度出てくるのかとか、もし出てきた場合に今まで出来たやつと同じになったらどうなるのかというのは疑問だけど無視して通った。

















解法:

BIT 4つ作った。

  • 1つ目のBITはとりあえず普通のBITで普通に1足す。(1つだけ独立して存在していると考える)
  • 2つ目のBITは、あるpについて、a_pが最大(右端)のときの、2つの場合の組み合わせ数を求める。
  • 3つ目のBITは、2つ目のBITの結果を利用して、qについて同様にa_qが最大のときに3つの大小関係が成り立っている組み合わせを2つ目のBITを利用して求める。
  • 4つ目のBITは、3つ目のBITの結果を利用して、同様にして4つの大小関係が成り立っている場合の組み合わせ数を求める。
  • 4つ目のBITの結果使ったら5つの大小関係成り立ってるやつの組み合わせ数求めるのでウッヒョー。
  • そしてこれ微妙に多倍長超えて不快なのでlong doubleで誤魔化す。long longでやったほうがよかったらしい。
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

typedef unsigned int uint;
int in() {
    int x = 0, c;
    for (; (uint)((c = getchar()) - '0') >= 10; ) { if (c == '-') return -in(); if (!~c) throw ~0; }
    do { x = (x << 3) + (x << 1) + (c - '0'); } while ((uint)((c = getchar()) - '0') < 10);
    return x;
}


struct I128{ //I128ぃ...(大嘘)
	long double a,b;
	static const long double limit = 1e15;
	static const long double EPS   = 1e-10;
	I128 operator + (const I128 &B) const{
		I128 copy = *this;
		copy.a += B.a , copy.b += B.b;
		copy.reflesh();
		return copy;
	}
	I128 operator += (const I128 &B){ return *this = (*this) + B; }
	
	void reflesh(){
		int overflow = (int)(b/limit);
		a += overflow * limit;
		b -= overflow * limit;
	}
	string toString(){
		char c[128];
		if(a < EPS) sprintf(c,"%.0Lf",b);
		else sprintf(c,"%.0Lf%015.0Lf",a/limit+1e-10,b);
		return string(c);
	}
	I128(unsigned long long n=0){ a=0,b=n; reflesh(); }
};

I128 bit[4][50001];
int num[50000];
int inp[50000];
int n;

inline I128 add(I128 bit[50001],int x,I128 val){ while(x <= n) bit[x] += val, x += x & -x; }
inline I128 get(I128 bit[50001],int x){ I128 get = 0; while(x){ get += bit[x]; x -= x & -x; } return get; }


int main(){
	while(~scanf("%d",&n)){
		memset(bit,0,sizeof(bit));
		memset(usd,0,sizeof(usd));
		for(int i = 0 ; i < n ; i++)
			num[i] = inp[i] = in();
		sort(num,num+n);
		I128 answer=0;
		for(int i = 0 ; i < n ; i++){
			int val = lower_bound(num,num+n,inp[i]) - num + 1;
			add(bit[0],val,I128(1));
			add(bit[1],val,get(bit[0],val-1));
			add(bit[2],val,get(bit[1],val-1));
			add(bit[3],val,get(bit[2],val-1));
			answer += get(bit[3],val-1);
		}
		cout << answer.toString() << endl;
	}
}