HJ98. 喜欢切数组的红
题目描述
小红有一个长度为 n 的数组，她打算将数组切两刀变成三个非空子数组，使得每一个子数组中至少存在一个正数，且每个子数组的和都相等。
求一共有多少种不同的切分方案。
输入格式
- 第 1 行：数组长度 n
- 第 2 行：n 个整数（可为负数、零、正数）
输出格式
一个整数，表示满足条件的切分方案数。
示例
示例 1
输入：
3
3 3 3
输出：
1
说明：
切成 [3] | [3] | [3]，三段和都为 3 且各含正数。
示例 2
输入：
6
1 1 4 5 1 4
输出：
0
示例 3
输入：
10
0 3 4 2 3 2 1 -1 3 4
输出：
2
解题思路
第一步：理解问题本质
切两刀成三段，需要满足三个条件：
- 三段和相等 → 每段和 = 总和/3
- 三段都非空
- 每段至少含一个正数
三段和相等等价于：存在切点 i < j 使得前缀和 pre[i] == m、pre[j] == 2m（其中 m = total/3）。
第二步：暴力解法
枚举所有 (i, j) 切点，计算三段和与各段正数个数，逐个判断。O(n²) 且要反复求和，大数据下超时。
第三步：前缀和 + 正数计数优化
用前缀和数组 pre 和正数个数前缀数组 pos，把"区间和"和"区间是否含正数"都变成 O(1) 查询：
- 第一段含正数：
pos[i] > 0 - 中间段含正数：
pos[j] - pos[i] > 0 - 第三段含正数：
pos[n] - pos[j] > 0
第四步：最优解法（扫描 + 树状数组）
对每个合法的 j（pre[j] == 2m 且第三段含正数），需要统计满足以下条件的 i 个数：
i < j，pre[i] == m，pos[i] > 0，且pos[i] < pos[j]
从左到右扫描位置 p，用树状数组维护已见到的合法 i 的 pos 值。遇到 j 时查询 pos 值 < pos[j] 的个数累加到答案。O(n log n)。
完整代码实现
算法可视化 · 逐帧回放这道题的代码49 帧 · 录制输入
import sys
class Fenwick:
def __init__(self, n):
self.n = n
self.bit = [0] * (n + 2)
def add(self, idx, val):
idx += 1
while idx <= self.n + 1:
self.bit[idx] += val
idx += idx & -idx
def query(self, idx):
idx += 1
s = 0
while idx > 0:
s += self.bit[idx]
idx -= idx & -idx
return s
def solve():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
total = sum(a)
if total % 3 != 0:
print(0)
return
m = total // 3
pre = [0] * (n + 1)
pos = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i - 1]
pos[i] = pos[i - 1] + (1 if a[i - 1] > 0 else 0)
if pos[n] == 0:
print(0)
return
bit = Fenwick(n + 1)
ans = 0
for p in range(1, n):
if pre[p] == 2 * m and pos[n] - pos[p] > 0:
ans += bit.query(pos[p] - 1)
if pre[p] == m and pos[p] > 0:
bit.add(pos[p], 1)
print(ans)
if __name__ == "__main__":
solve()
示例推演
以示例 3 [0,3,4,2,3,2,1,-1,3,4] 为例：
总和 = 21，m = 7，2m = 14。
前缀和 pre：
| 位置 p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| pre | 0 | 3 | 7 | 9 | 12 | 14 | 15 | 14 | 17 | 21 |
| pos | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 6 | 7 | 8 |
- 合法
i（pre == 7且pos[i]>0）：位置 3，pos=2 - 合法
j（pre == 14且第三段含正数pos[10]-pos[j]>0）：位置 6（pos=5）、位置 8（pos=6）
扫描：
- 位置 6（j）：此时已加入的
i只有位置 3（pos=2）。pos[j]=5，需pos[i]<5，位置 3 满足 → 贡献 1。 - 位置 8（j）：
pos[j]=6，位置 3 的pos=2<6→ 贡献 1。
结果：2。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 超时 |
| 前缀和优化 | O(n²) | O(n) | 仍需枚举 |
| 扫描 + 树状数组 | O(n log n) | O(n) | 最优 |
n 为数组长度
易错点总结
1. 忘记"每段含正数"
仅三段和相等不满足题意，必须同时保证三段各自至少有一个正数。
2. 总和必须能被 3 整除
若 total % 3 != 0，直接输出 0，提前返回。
3. i < j 的严格性
第一段末尾 i 必须严格小于第二段末尾 j，保证中间段非空。扫描时先查询 j 再加入同位置的 i 可避免 i==j 被误计。
4. 负数与零
数组含负数和 0，pos 只统计 > 0 的数；区间含正数等价于 pos 差分大于 0。
扩展思考
- 用树状数组维护
pos值实现"计数 pos[i] < pos[j]"是该题的关键技巧，也可推广到二维偏序计数。 - 若去掉"每段含正数"约束，题目退化为纯前缀和计数，可直接 O(n) 完成。