题解 P2309 【loidc,卖卖萌】
Tomone
2018-10-15 16:15:48
那么..前面的都讲清楚了
我来发个树状数组
```cpp
#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;
}
```