题解 | 喜欢切数组的红（前缀和）

#牛客春招刷题训练营# + 链接

1.区间和的条件不好处理，转换为总和的三分之一以及前缀和。

2.区间内至少有一个正数，转换为下一个正数的索引。

3.向后计数，转换为计数的后缀和。

#include <iostream>
using namespace std;

using ll = long long;

const int MAXN=200010;
int a[MAXN], ddr[MAXN], np[MAXN];
ll s[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d",a+i);
    for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    int x=n+1;
    for (int i=n;i>0;i--) {
        np[i] = x;
        if (a[i]>0) x=i;
    }
    ll mm = s[n]/3;
    if (mm*3!=s[n]) {
        puts("0");
        return 0;
    }
    ll ans=0;
    for (int i=n;i>0;i--) {
        ddr[i] = ddr[i+1]+ (s[i]==mm*2);
    }
    for (int i=1;i<=n;i++) {
        if (s[i]==mm) ans+=ddr[np[i]];
    }
    printf("%lld\n", ans);
    return 0;
}