一、题意整理（关键约束）

给定数组 $a$，满足条件：

$$\max(|a_i|) \le \sum_{i=1}^n a_i$$

我们需要构造数组 $b$，满足：

1. $a$ 是 $b$ 的子序列。
2. $\sum a = \sum b$（总和不变）。
3. $b$ 的最大子段和（无聊值）尽可能小。
4. 在满足条件3的前提下，$b$ 的长度 $m$ 尽可能小。

求：最终数组 $b$ 的最小长度 $m$。

---

二、核心结论（解题关键）

这道题的本质是：用最少的插入次数，消除所有会导致最大子段和超标的区间。

1. 最大子段和下界

题目给出的约束 $\max(|a_i|) \le \sum a$ 保证了：

• 数组总和 $S = \sum a > 0$
• 我们能构造出 $b$，使其最大子段和严格等于 $S$（这是理论最小值，无法更小）。

2. 最小长度公式（标程核心）

最终答案：

$$\boldsymbol{m = n + v + extra}$$

• $n$：原数组长度
• $v$：标程中统计的需要插入分隔的段数
• $extra$：最后一段是否需要补 $0$ 或 $1$ 个分隔（r != p）

---

三、算法思路（标程逻辑）

我们遍历数组，维护两个变量：

• $l$：当前区间可达的最小前缀和
• $r$：当前区间可达的最大前缀和
• $p = S$：数组总和

规则

1. 遇到正数

   • 扩大区间：$l += a_i,\ r = \min(r + a_i,\ p)$
   • 若 $l > r$，说明必须插入元素分隔，$v \boldsymbol{+}= 1$。

2. 遇到负数

   • 缩小区间：$r -= |a_i|,\ l = \max(l - |a_i|,\ 0)$
   • 若 $l > r$，说明必须插入元素分隔，$v \boldsymbol{+}= 1$。

3. 最终答案

   $$m = n + v + (r \neq p)$$

---

四、标程代码逐行详解

#include <bits/stdc++.h>
 
namespace FastIO {
	// 快速读写模板（应对大数据输入）
	template <typename T> inline T read() { ... }
	template <typename T> inline void write(T x) { ... }
}; using namespace FastIO;
 
#define MAXN 3000001
int a[MAXN]; // 数组开足 3e6 空间

---

核心函数 solve()

void solve() {
	int N = read<int>();         // 读入数组长度 n
	long long p = 0, l = 0, r = 0, v = 0;

	// 第一步：计算数组总和 p = sum(a)
	for (int i = 1; i <= N; ++i)
		p += (a[i] = read<int>());

	// 第二步：遍历数组，维护 [l, r] 区间
	for (int i = 1; i <= N; ++i) {
		if (a[i] >= 0) {
			// 处理正数
			l += a[i];
			r = std::min(r + a[i], p);
			
			// 区间非法 → 必须插入分隔，v+1
			if (l > r) {
				++v;
				l = a[i];
				r = p;
			}
		} else {
			// 处理负数，取绝对值
			a[i] = -a[i];
			r -= a[i];
			l = std::max(l - a[i], 0ll);
			
			// 区间非法 → 必须插入分隔，v+1
			if (l > r) {
				++v;
				l = 0;
				r = p - a[i];
			}
		}
	}

	// 第三步：计算最终答案
	print<int>(v + N + (int)(r != p), '\n');
}

---

五、公式解释（最关键）

$$\boldsymbol{m = n + v + (r \neq p)}$$

1. $n$：原数组必须完整保留。
2. $v$：每触发一次区间非法，必须插入 1 个元素分隔。
3. $(r \neq p)$：最后一段如果没有闭合，额外补 1 个插入。

---

六、样例验证

样例 2

输入：

4
2 -3 2 2

• $n=4$
• 遍历过程触发 $v=2$
• 最后 $r \neq p$，补 $1$
• 答案：$4 + 2 + 0 = \boldsymbol{6}$（与样例完全一致）

---

七、时间复杂度

• 每组用例：$O(n)$
• 总 $n$ 之和 $\le 3\times10^6$
• 完美适配 3 秒时限

---

八、总结（一句话记住）

1. 目标：让最大子段和 $= S$（总和）。
2. 方法：遍历维护前缀和区间 $[l, r]$。
3. 统计：区间非法时 $v+1$（必须插入）。
4. 答案：$\boldsymbol{m = n + v + (r \neq p)}$。

---