题解 | 喜欢切数组的红

// 前缀和，后缀和，前缀数和，前缀正数个数和，后缀正数个数和，unordered_map，记录<后缀和,下标>
// 会卡总和不是 3 的倍数的优化
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+6;
long long qsum[N];
unordered_multimap<int,int> unmp;
int n;
int arr[N],qzs[N],hzs[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        qsum[i]=qsum[i-1]+arr[i];
        if(arr[i]>0) qzs[i]=qzs[i-1]+1;
        else qzs[i]=qzs[i-1];
    }
    int sum=0;
    for(int i=n;i>=1;i--){
        sum+=arr[i];
        if(arr[i]>0) hzs[i]=hzs[i+1]+1;
        else hzs[i]=hzs[i+1];
        if(hzs[i]>0) unmp.insert({sum,i});
        
    }
    if(sum%3!=0){
        cout<<0;
        return 0;
    }
    int ans=0,zs_sum=qzs[n];
    // cout<<qzs[n]<<" "<<hzs[1]<<endl;
    for(int i=1;i<=n;i++){
        if(qzs[i]<1 || qsum[i]*3!=sum) continue;
        int x=qsum[i];
        if(unmp.count(x)>0 && sum-x-x==x){
            auto p=unmp.find(x);
            for(int j=0;j<unmp.count(x);j++){
                int idx=p->second;
                if(zs_sum-qzs[i]-hzs[idx]>0 && 
                qzs[i]>0 && idx-i>1) ans++;
                p++;
            }
        }
    }
    cout<<ans;

    return 0;
}