奶牛抗议分组(Generic Cow Protests G) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

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

const int MOD = 1000000009;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> pref(n + 1, 0), vals;
    vals.push_back(0);
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        pref[i] = pref[i - 1] + a;
        vals.push_back(pref[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();
    vector<int> bit(m + 1, 0);
    auto add = [&](int idx, int v) {
        for (int i = idx; i <= m; i += i & -i) {
            bit[i] += v;
            if (bit[i] >= MOD) bit[i] -= MOD;
        }
    };
    auto query = [&](int idx) {
        int s = 0;
        for (int i = idx; i > 0; i -= i & -i) {
            s += bit[i];
            if (s >= MOD) s -= MOD;
        }
        return s;
    };
    int rk0 = (int)(lower_bound(vals.begin(), vals.end(), 0LL) - vals.begin()) + 1;
    add(rk0, 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int rk = (int)(lower_bound(vals.begin(), vals.end(), pref[i]) - vals.begin()) + 1;
        ans = query(rk);
        add(rk, ans);
    }
    cout << ans << "\n";
    return 0;
}