题解 | 喜欢切数组的红

#include <iostream>
#include <vector>
using namespace std;

class EqualSplit {
public:
    // 构造函数，传入数组长度与数组本体
    EqualSplit(int n, const vector<long long>& arr) : n(n), a(arr) {}

    // 对外提供的主计算接口
    long long countValidSplits() {
        return compute();
    }

private:
    int n;  // 数组长度
    vector<long long> a;  // 数组本体

    // 主计算函数，仅类内部调用
    long long compute() {
        long long total = 0;
        for (auto val : a) total += val;

        // 若无法被3整除，则无解
        if (total % 3 != 0) return 0;

        long long target = total / 3;

        // 构建前缀和
        vector<long long> prefix(n);
        prefix[0] = a[0];
        for (int i = 1; i < n; ++i) {
            prefix[i] = prefix[i - 1] + a[i];
        }

        // 构建前缀正数数量统计
        vector<int> pos_count(n);
        pos_count[0] = (a[0] > 0 ? 1 : 0);
        for (int i = 1; i < n; ++i) {
            pos_count[i] = pos_count[i - 1] + (a[i] > 0 ? 1 : 0);
        }

        // 构建后缀是否包含正数数组
        vector<bool> has_pos_suffix(n);
        has_pos_suffix[n - 1] = (a[n - 1] > 0);
        for (int i = n - 2; i >= 0; --i) {
            has_pos_suffix[i] = has_pos_suffix[i + 1] || (a[i] > 0);
        }

        long long ans = 0;

        // 枚举第二刀（第二段结束位置）
        for (int i = 1; i < n - 1; ++i) {
            // 前缀和为 2 * target，且后缀（第三段）包含正数
            if (prefix[i] == 2 * target && has_pos_suffix[i + 1]) {
                // 枚举第一刀位置 j < i
                for (int j = 0; j < i; ++j) {
                    // 第一段和为 target 且包含正数
                    if (prefix[j] == target && pos_count[j] > 0) {
                        // 第二段需包含正数：[j+1..i]
                        int pos_in_middle = pos_count[i] - pos_count[j];
                        if (pos_in_middle > 0) {
                            ans++;
                        }
                    }
                }
            }
        }

        return ans;
    }
};

// 主函数入口
int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 创建 EqualSplit 对象，执行计算
    EqualSplit solver(n, a);
    cout << solver.countValidSplits() << endl;

    return 0;
}