Codeforces #187 Div1. C. Sereja and Subsequences

さてC。これはEditorial無しだとちょっときつかった。
http://codeforces.com/contest/314/problem/C

問題

整数列A[i]が与えられる。
この数列からいくつか要素を抜き出したdistinctな非減少数列Xを作る。
ここで数列Xに対し、同じ長さの数列Yを作り、1<=Y[i]<=X[i]となるようにしたい。

X,Yの組み合わせを答えよ。

解法

Xの最大値がPとなるようなX,Yの組み合わせの数をF[P]とする。
Aの要素を順に見ていき、XにA[i]を追加できるのは、Xが空の時かXの最大値がA[i]以下の時である。
また、XにA[i]を追加すると、Y[i]の選択肢がY個できる。

よって、F[A[i]] += A[i] * (1+F[1]+F[2]+...+F[A[i]])となる。
上記処理では数列の部分和を頻繁に求めるので、BITを使った。

ll mo=1000000007;

template<class V, int ME> class BIT {
public:
	V* bit;
	BIT(){bit=new V[ME];memset(bit,0,sizeof(V)*ME);}
	
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) {
			s+=bit[entry-1];
			entry -= entry & -entry;
		}
		return s % mo;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= ME) {
			bit[entry-1] = (bit[entry-1] + val) % mo;
			entry += entry & -entry;
		}
	}
};
BIT<ll,1<<20> bit;

void solve() {
	int f,r,i,j,k,l, x,y;
	ll ret = 1;
	
	cin>>j;
	FOR(i,j) {
		cin>>x;
		bit.update(x, (x+bit.total(x)*x-(bit.total(x)-bit.total(x-1)))%mo);
	}
	
	cout << bit.total(1<<20) << endl;

	return;
}

まとめ

自分で作ったBITの使いこなしに手こずってしまった。