E题题解：

时间复杂度O(n)哦！

题目大意：

给数组切 2 刀，每份总和相等，都要包含正数

思路：

首先定义一个前缀和数组 sum，sum[i]=a[1]+a[2]+...+a[i]。

如果 sum[n] 不是三的倍数，怎么切，都不行。

直接考虑第一刀砍在 i，i+1 之间，求右边能切的位置数量，需要满足下面几点：

1. sum[i] == sum[n]/3

定义一个前缀和数组 ne，ne[j]=(a[1]>0)+(a[2]>0)+...+(a[j]>0)，表示从 1~j 有几个正数。

2. ne[i] > 0

那右边能切的位置数量如何求？

我们从后往前推，记录切在 i~n 之间，使得右边的序列（总和也要为 sum[n]/3）包含正数的刀数，记为 f[i]。

能想到这么个式子：

for(int i=n;i;i--)
    f[i]=f[i+1]+(ne[n]-ne[i-1]&&sum[n]-sum[i-1]==s[n]/3);

最后，两端总数都等于 sum[n]/3 ，中间一段序列总数必然为 sum[n]/3。

因为中间一段序列也要包含正数，定义一个 nt 数组，nt[n+1]=n+1 ，nt[i]=a[i]>0?i:nt[i+1]，表示从 i 往后的第一个正数在哪里，如果第一刀切在i | i+1，那么第二刀需要切在 nt[i+1] 之后。

得出最终式子：

for(ll i=1;i<=n;i++)
    if(ne[i]&&sum[i]==sum[n]/3){
        ll r=nt[i+1];
        if(r<n) ans+=f[r+1];
    }

最后输出 ans 即可，时间复杂度

代码：

#include<bits/stdc++.h>
#define ll long long
#define MXN 1000002
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
ll T=1,n,a[MXN],ne[MXN],nt[MXN],sum[MXN],f[MXN],ans;
void solve(){
    rd(n);
    for(ll i=1;i<=n;i++)
        rd(a[i]),ne[i]=ne[i-1]+(a[i]>0),sum[i]=sum[i-1]+a[i];
    if(sum[n]%3){puts("0");return;}
    nt[n+1]=n+1;
    for(ll i=n;i;i--)
        f[i]=f[i+1]+(ne[n]-ne[i-1]&&sum[n]-sum[i-1]==sum[n]/3),
        nt[i]=a[i]>0?i:nt[i+1];
    for(ll i=1;i<=n;i++)
        if(ne[i]&&sum[i]==sum[n]/3){
            ll r=nt[i+1];
            if(r<n) ans+=f[r+1];
        }
    pt(ans);
}int main(){while(T--) solve();}