C. Good Prefixes 详细题解

题目重述

给定一个长度为 $n$ 的数组 $a$，定义数组 $[x_1, x_2, \dots, x_m]$ 是“好的”，如果存在某个元素等于其余所有元素的和（若没有其他元素，则和为 $0$）。例如 $[1,6,3,2]$ 是好的因为 $6 = 1+3+2$。需要统计数组 $a$ 的所有非空前缀中，有多少个是好的。

核心观察

对于一个长度为 $i$ 的前缀 $[a_1, a_2, \dots, a_i]$，设其总和为 $S_i = \sum_{j=1}^{i} a_j$。该前缀是好的当且仅当存在某个下标 $p$（$1 \le p \le i$），使得：

这是因为“其余元素的和”等于总和减去该元素本身。所以条件等价于 $S_i$ 是偶数且 $a_p = S_i/2$ 对于某个 $p$ 成立。

因此，前缀 $i$ 是好的 $\iff$ $S_i$ 为偶数且 $S_i/2$ 出现在前缀 $i$ 的元素中（即 $S_i/2$ 等于某个 $a_j$，$1 \le j \le i$）。

算法思路

我们顺序扫描数组，维护：

• 当前前缀和 $sum$。
• 一个哈希集合（或布尔数组）$seen$，存储当前前缀中已经出现过的元素值。

对于每个位置 $i$（从 $1$ 到 $n$）：

1. 将 $a_i$ 加入 $sum$，同时将 $a_i$ 插入 $seen$。
2. 检查 $sum$ 是否为偶数，并且 $sum/2$ 是否在 $seen$ 中。若是，则当前前缀是好的，答案加 $1$。

由于 $n$ 可达 $2\times 10^5$，且所有测试用例的总 $n$ 不超过 $2\times 10^5$，该算法 $O(n)$ 时间，$O(n)$ 空间（哈希集合），完全可行。

正确性证明

• 必要性：如果前缀 $i$ 是好的，则存在 $p$ 使得 $a_p = \sum_{j\neq p} a_j = S_i - a_p$，推出 $2a_p = S_i$，故 $S_i$ 为偶数且 $S_i/2 = a_p$，因此 $S_i/2$ 必然出现在前缀中。
• 充分性：若 $S_i$ 为偶数且 $S_i/2$ 等于某个 $a_p$（$1 \le p \le i$），则 $a_p = S_i/2$，其余元素的和为 $S_i - a_p = S_i/2 = a_p$，满足定义。因此前缀 $i$ 是好的。

所以判断条件正确。

复杂度分析

• 每个测试用例遍历一次数组，每个元素进行一次哈希集合插入和查询，时间复杂度 $O(n)$。
• 空间复杂度 $O(n)$ 用于存储集合中的元素。
• 所有测试用例的 $n$ 总和 $\le 2\times 10^5$，总体复杂度非常快。

示例验证

以第四个测试用例 $a = [0,1,2,1,4]$ 为例：

• $i=1$：$sum=0$，偶数，$0/2=0$ 在集合中（$0$ 出现），计数 $+1$。
• $i=2$：$sum=1$，奇数，不满足。
• $i=3$：$sum=3$，奇数，不满足。
• $i=4$：$sum=4$，偶数，$2$ 在集合中（$a_3=2$），计数 $+1$。
• $i=5$：$sum=8$，偶数，$4$ 在集合中（$a_5=4$），计数 $+1$。 总数 $=3$，与输出一致。

注意事项

• $a_i$ 可以为零，此时 $S_i$ 可能为偶数且 $S_i/2=0$，若 $0$ 出现过（一定出现过，因为 $a_1$ 可能为 $0$），则前缀被认为是好的。例如 $[0]$ 是好的，符合题意。
• 由于元素值可达 $10^9$，使用 long long 存储和，并使用 unordered_set 或 map 存储出现过的值。

总结

本题的关键在于将“存在某个元素等于其余元素的和”转化为 $2a_p = S_i$，从而只需检查 $S_i$ 是否为偶数且 $S_i/2$ 是否已出现。通过顺序扫描并维护哈希集合，可以在线性时间内统计所有好前缀的个数。该方法简单高效，适用于较大的数据范围。