题解 | 喜欢切数组的红

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    long long total = 0;
    for (auto val : a) total += val;
    if (total % 3 != 0) {
        cout << 0 << endl;
        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];

    // 正数前缀和数组：pos_count[i] 表示 [0..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);
    }

    // 每个前缀和为 target 的合法切点数（且该段含正数）
    vector<int> valid_cut_count(n, 0);
    int count = 0;
    for (int i = 0; i < n - 2; ++i) {
        if (prefix[i] == target && pos_count[i] > 0) {
            count++;
        }
        valid_cut_count[i] = count;
    }

    long long ans = 0;

    for (int i = 1; i < n - 1; ++i) {
        if (prefix[i] == 2 * target && has_pos_suffix[i + 1]) {
            // 要判断第二段是否有正数：[j+1 .. i] -> [0..i] - [0..j]
            // 我们从前面记录的 valid_cut_count[i-1] 是所有合法 j <= i-1
            // 现在我们只要排除那些 j 的切法中 j+1..i 没有正数的就行了

            // 枚举所有 prefix[j] == target 且 j < i
            // 因为我们不能再 O(n) 枚举了，我们估算第二段含正数的条件：

            // 当前位置 i，前缀正数个数：pos_count[i]
            // 合法第一段结尾 j 的位置数量：valid_cut_count[i - 1]

            // 为了保证第二段 [j+1..i] 有正数：
            // 对于每一个 j 满足 prefix[j] == target 且 pos_count[i] - pos_count[j] > 0
            // 用滑动窗口（双指针可进一步优化）

            // 简化处理：暴力尝试每个合法 j，直到 i（只考虑 prefix[j] == target 且段含正数）

            for (int j = 0; j < i; ++j) {
                if (prefix[j] == target && pos_count[j] > 0) {
                    // 判断 [j+1..i] 是否含正数
                    int pos_in_segment = pos_count[i] - pos_count[j];
                    if (pos_in_segment > 0) {
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}