5962번: Generic Cow Protests

https://www.acmicpc.net/problem/5962


$O(n\lg n)$

s[i]: 1...i 번째 수들의 합
t[i]: 1...i 번째 수들로 그룹을 짓는 경우의 수
t[i]=sum(s[j]<=s[i])(t[j])
조건을 만족하는 j에 대한 t[j]의 합은 펜윅 트리로 빠르게 구할 수 있다.

#include<cstdio>
#include<algorithm>
#define mod 1000000009
using namespace std;
const int MXN = 1e5;
int idx[MXN + 1], s[MXN + 1], bit[MXN + 2], sz = 1, n, p, t;
void update(int h, int x) {
    for (; h <= sz; h += h&-h) bit[h] = (bit[h] + x) % mod;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s = (s + bit[h]) % mod;
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", s + i), idx[sz++] = s[i] += s[i - 1];
    sort(idx, idx + sz);
    sz = unique(idx, idx + sz) - idx;
    update(lower_bound(idx, idx + sz, 0) - idx + 1, 1);
    for (int i = 1; i <= n; i++) {
        p = lower_bound(idx, idx + sz, s[i]) - idx + 1;
        t = query(p);
        update(p, t);
    }
    printf("%d", t);
    return 0;
}