RT

code

#include<bits/stdc++.h>
#define MAXN 100005
std::mt19937 rnd(2333);
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 9;
ll N;
ll sum[MAXN], F[MAXN];

struct Node{
	ll val, siz, key, lc, rc, dat, sum;
} tree[MAXN];

ll tot, root;

inline ll build(ll val, ll id) {
	tree[++tot].key = rnd();
	tree[tot].siz = 1;
	tree[tot].val = val;
	tree[tot].dat = F[id];
	tree[tot].sum = F[id];
	return tot;
}

inline void pushup(ll x) {
	tree[x].siz = tree[tree[x].lc].siz + tree[tree[x].rc].siz + 1;
	tree[x].sum = tree[tree[x].lc].sum + tree[tree[x].rc].sum + tree[x].dat;
}

inline void split(ll p, ll val, ll &x, ll &y) {
	if (p == 0) {
		x = y = 0;
		return;
	}
	if (tree[p].val <= val) {
		x = p;
		split(tree[p].rc, val, tree[p].rc, y);
	} else {
		y = p;
		split(tree[p].lc, val, x, tree[p].lc);
	}
	pushup(p);
}

inline ll merge(ll x, ll y) {
	if (!x || !y) return x + y;
	if (tree[x].key > tree[y].key) {
		tree[x].rc = merge(tree[x].rc, y);
		pushup(x);
		return x;
	} else {
		tree[y].lc = merge(x, tree[y].lc);
		pushup(y);
		return y;
	}
}

inline void insert(ll val, ll id) {
	ll T1, T2;
	split(root, val - 1, T1, T2);
	root = merge(merge(T1, build(val, id)), T2);
}

inline void del(ll val) {
	ll T1, T2, T3;
	split(root, val, T1, T3);
	split(T1, val - 1, T1, T2);
	if (T2) T2 = merge(tree[T2].lc, tree[T2].rc);
	root = merge(merge(T1, T2), T3);
}

inline ll get(ll val) {
	ll T1, T2;
	split(root, val, T1, T2);
	ll sum = tree[T1].sum;
	root = merge(T1, T2);
	return sum;
}

int main() {
	#ifdef LOCAL // 525989139
	freopen("test.in", "r", stdin);
	#endif
	scanf("%lld\n", &N);
	for (ll i = 1; i <= N; ++i) {
		scanf("%lld", sum + i);
 		sum[i] += sum[i - 1];
 	}
 	for (ll i = 1; i <= N; ++i) {
 		if (sum[i] >= 0) F[i] = 1;
 		F[i] += get(sum[i]);
 		F[i] %= MOD;
 		insert(sum[i], i);
 	}
	printf("%lld\n", F[N]);
	return 0;
}