Codeforces 314C Sereja and Subsequences

問題

長さnの数列a[i]が与えられる。
a[i]の空でない、（必ずしも連続しない）非減少部分列のうち、異なるものを全て取り出す。
それぞれに対して、それより"小さな"列の個数を求め、足し合わせる。

個数の総和はいくつか。
ただし、列xiよりyiが小さいである列というのは、xとyの長さが同じで、
yiが正であり、各iについてxi≧yiが成り立つことを言うものとする。

制約条件

n≦10^5
a[i]≦10^6

方針

DPで数えればよいのだが、取り出す非減少列がユニークでなくてはならないので
その部分をきちんと数えるのに工夫が必要。

dp[i]を、a[i]を最後に使ったもユニークな列について、それよりも小さな列の総数とする

。
dp[i]は、iまでに列挙したどの列に対して付け加えられるかと考えると、
a[j]＞a[i]であるようなjについては付け足せない。
a[j]≦a[i]であるようなjについては、
j＜k＜iでありa[k] = a[i]となるようなkがあったら付け足せない。

これはどういうことかというと
i : 0 1 2 3 4 5
a : 2 3 3 2 2 3
みたいな列があったら、a[2]はa[0]の後には付け足せないということ。
付け足すと、a[0]a[2]とa[0]a[1]が重複してしまうため。

ということで、どうしたらいいかというと、
数字ごとに、今までに付け足せた候補の場所の個数を記録しておいて、
付け足すときには、候補全体から、同じ数字における今までの候補の個数を引いてやればよい。

数字の重複がない場合は、
a[j]＜a[i]であるようなj全部に付け足せるので、これはbinary indexed treeなどで和を管理すればいい。

ソースコード

const int MX = 1000100, mod = (int)1e9 + 7;

int n, a[100000], bit[MX], prev[MX];
inline void add(int i, int x){
	for(; i < MX; i += i & -i) (bit[i] += x) %= mod;
}
inline int sum(int i){
	ll res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res % mod;
}
int main(){
	add(1, 1);
	cin >> n;
	rep(i, n) cin >> a[i];
	
	ll ans = 0;
	rep(i, n){
		ll p = (sum(a[i] + 1) + mod - prev[a[i]]) % mod;
		
		prev[a[i]] = (prev[a[i]] + p) % mod;
		p = p * a[i] % mod;
		ans += p;
		add(a[i] + 1, p);
	}
	
	cout << ans % mod << endl;
	return 0;
}