题解 P2309 【loidc,卖卖萌】

2018-10-15 16:15:48


那么..前面的都讲清楚了 我来发个树状数组

#include <iostream>
#include <algorithm>
#define lowbit(x) x & -x
using namespace std;
typedef long long LL;
const LL MAXN = 100005;

LL n,len;
LL s[MAXN],a[MAXN],ans,c[MAXN],b[MAXN];
inline void add(LL x) {
    while(x <= n) {
        c[x]++;
        x += lowbit(x);
    }
}
inline LL sum(LL x) {
    LL Ans = 0;
    while(x) {
        Ans += c[x];
        x -= lowbit(x);
    }
    return Ans;
}
inline LL get_id(const LL &x) {
    return lower_bound(b + 1,b + 1 + len,x) - b;
}

inline LL Work() {
    LL Ans = 0;
    for(LL i = 1;i <= n;++i) b[i] = s[i];
    sort(b + 1,b + 1 + n);
    len = unique(b + 1,b + 1 + n) - b - 1;
    for(LL i = 1;i <= n;++i) {
        add(get_id(s[i]));
        Ans += sum(n) - sum(get_id(s[i]));
    }
    return Ans;
}

int main() {
    cin >> n;
    for(LL i = 1;i <= n;++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for(LL i = 1;i <= n;++i) {
        s[i] = -s[i];
        if(s[i] < 0) ans++;
    }
    cout << Work() + ans << endl;
}