第一次题解发布

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 100005;
const int MOD = 1000000009;

long long n, a[MAXN], dp[MAXN];
long long tree[MAXN * 2];
long long b[MAXN];
int m;

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

void update(int x, long long val) {
while (x <= m) {
tree[x] = (tree[x] + val) % MOD;
x += lowbit(x);
}
}

long long query(int x) {
long long res = 0;
while (x > 0) {
res = (res + tree[x]) % MOD;
x -= lowbit(x);
}
return res;
}

int get_index(long long v) {
return lower_bound(b + 1, b + m + 1, v) - b;
}

int main() {
cin >> n;
a[0] = 0;
for (int i = 1; i <= n; i++) {
int z;
cin >> z;
a[i] = a[i-1] + z;
}

// 离散化前缀和值 a[0] 到 a[n-1]
for (int i = 0; i < n; i++) {
    b[i+1] = a[i];
}
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - b - 1;

memset(tree, 0, sizeof(tree));

// 从右向左计算 dp[i]
for (int i = n; i >= 1; i--) {
    if (a[n] - a[i-1] < 0) {
        dp[i] = 0;
    } else {
        int idx = get_index(a[i-1]);
        long long S = (query(m) - query(idx - 1)+MOD) % MOD;
        dp[i] = (1 + S) % MOD;
    }
    int idx_ins = get_index(a[i-1]);
    update(idx_ins, dp[i]);
}

cout << dp[1] << endl;

return 0;

}