题目解析

问题重述

给定一个数组 $a$，其中除了最多一个元素外，其余元素都是 $1$ 或 $-1$。那个特殊的元素 $x$ 可以是任意整数（$-10^9 \le x \le 10^9$）。需要找出所有可能的子段和（包括空子段，和为 $0$），按升序输出。

核心思路

1. 简化问题：全是 $1$ 或 $-1$

如果所有元素都是 $1$ 或 $-1$，那么对于任意固定左边界 $l$，随着右边界 $r$ 向右移动，子段和每次变化 $\pm 1$。因此，从该左边界出发可以得到从最小值到最大值的所有整数。由于所有子段都包含空子段（和为 $0$），所有可能子段和的并集也是一个连续的区间 $[minSum, maxSum]$。

所以，当数组只有 $\pm 1$ 时，答案就是从最小子段和到最大子段和的所有整数。

2. 包含特殊元素的情况

数组最多有一个特殊元素 $x$（既不是 $1$ 也不是 $-1$）。将子段分为两类：

• 不包含特殊元素的子段：这些子段完全由 $\pm 1$ 组成，其和构成一个连续区间 $[L_1, R_1]$（包含 $0$）
• 包含特殊元素的子段：去掉特殊元素后，剩余部分由 $\pm 1$ 组成，其和构成一个连续区间 $[L_2, R_2]$（包含 $0$）。加上特殊元素后，和变为 $[L_2 + x, R_2 + x]$

3. 最终答案

最终所有可能的子段和是这两个区间的并集：

由于两个区间都是连续的整数区间，它们的并集可能是：

• 一个连续区间（如果有重叠或相邻）
• 两个分离的区间（如果没有重叠）

4. 如何求 $L_1, R_1, L_2, R_2$

利用前缀和技巧：子段 $[l, r]$ 的和 = $pref[r+1] - pref[l]$。

固定右边界 $r$，最大子段和 = $pref[r+1] - \min_{l \le r} pref[l]$，最小子段和 = $pref[r+1] - \max_{l \le r} pref[l]$。

遍历数组时，我们维护：

• 前缀和 $pr$
• 到当前位置为止的最小前缀和 $mnl$ 和最大前缀和 $mxl$
• 特殊元素出现前的最小/最大前缀和（用于不包含特殊元素的子段）
• 特殊元素出现后的最小/最大前缀和（用于包含特殊元素的子段）

算法步骤

1. 初始化：

   • $l_1 = 0, r_1 = 0$（不包含特殊元素的子段和范围）
   • $l_2 = \infty, r_2 = -\infty$（包含特殊元素的子段和范围）
   • $pr = 0$（当前前缀和）
   • $mnl = 0, mxl = 0$（到当前位置的最小/最大前缀和）
   • $mnr = \infty, mxr = -\infty$（特殊元素出现前的最小/最大前缀和）

2. 遍历数组：

   • 更新前缀和 $pr += a[i]$
   • 如果遇到特殊元素（$|a[i]| \neq 1$）：
     • 保存特殊元素前的范围：$mnr = mnl, mxr = mxl$
     • 重置特殊元素后的范围：$mnl = pr, mxl = pr$
   • 更新不包含特殊元素的子段和范围：
     • $l_1 = \min(l_1, pr - mxl)$
     • $r_1 = \max(r_1, pr - mnl)$
   • 更新包含特殊元素的子段和范围：
     • $l_2 = \min(l_2, pr - mxr)$
     • $r_2 = \max(r_2, pr - mnr)$
   • 更新最小/最大前缀和：
     • $mnl = \min(mnl, pr)$
     • $mxl = \max(mxl, pr)$

3. 根据区间关系合并结果：

   • 如果 $l_2 > r_1$：两个区间分离，$[l_1, r_1]$ 在前，$[l_2, r_2]$ 在后
   • 如果 $r_2 < l_1$：两个区间分离，$[l_2, r_2]$ 在前，$[l_1, r_1]$ 在后
   • 否则：两个区间有重叠，合并为一个区间 $[\min(l_1, l_2), \max(r_1, r_2)]$

4. 输出区间内的所有整数

示例验证

例1： $[1, -1, 10, 1, 1]$

• 不包含 $10$ 的子段：由 $\pm 1$ 组成，和的范围 $[-1, 2]$
• 包含 $10$ 的子段：去掉 $10$ 后剩下的 $\pm 1$ 部分和范围为 $[-1, 2]$，加上 $10$ 后为 $[9, 12]$
• 两个区间 $[-1, 2]$ 和 $[9, 12]$ 分离
• 结果：$-1, 0, 1, 2, 9, 10, 11, 12$ ✅

例2： $[-1, -1, -1, -1, -1]$

• 无不包含特殊元素（特殊元素不存在），$l_1 = -5, r_1 = 0$
• 包含特殊元素的子段范围不存在，$l_2 = \infty, r_2 = -\infty$
• 结果：$[-5, 0]$ 内所有整数 ✅

例3： $[-1, 2]$

• 不包含 $2$ 的子段：$[-1, 0]$
• 包含 $2$ 的子段：去掉 $2$ 后剩下 $[-1]$，范围 $[-1, -1]$，加上 $2$ 后为 $[1, 1]$
• 两个区间 $[-1, 0]$ 和 $[1, 1]$ 相邻（$0$ 和 $1$ 连续），合并为 $[-1, 1]$
• 结果：$-1, 0, 1$ ✅

时间复杂度

• 每个测试用例 $O(n)$
• $n$ 总和 $\le 2 \times 10^5$，总复杂度 $O(\sum n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 不包含特殊元素的子段和范围
        int l1 = 0, r1 = 0;
        // 包含特殊元素的子段和范围
        int l2 = 2e9, r2 = -2e9;
        
        int pr = 0;           // 当前前缀和
        int mnl = 0, mxl = 0; // 到当前位置的最小/最大前缀和
        int mnr = 2e9, mxr = -2e9; // 特殊元素出现前的最小/最大前缀和
        
        for (int i = 0; i < n; i++) {
            pr += a[i];
            
            if (abs(a[i]) != 1) {
                // 遇到特殊元素，保存特殊元素前的范围
                mnr = mnl;
                mxr = mxl;
                mnl = pr;
                mxl = pr;
            }
            
            // 更新不包含特殊元素的子段和范围
            l1 = min(l1, pr - mxl);
            r1 = max(r1, pr - mnl);
            
            // 更新包含特殊元素的子段和范围
            l2 = min(l2, pr - mxr);
            r2 = max(r2, pr - mnr);
            
            // 更新最小/最大前缀和
            mnl = min(mnl, pr);
            mxl = max(mxl, pr);
        }
        
        vector<int> res;
        
        // 合并两个区间
        if (l2 > r1) {
            // 区间分离：[l1, r1] 在前，[l2, r2] 在后
            for (int i = l1; i <= r1; i++) res.push_back(i);
            for (int i = l2; i <= r2; i++) res.push_back(i);
        } else if (r2 < l1) {
            // 区间分离：[l2, r2] 在前，[l1, r1] 在后
            for (int i = l2; i <= r2; i++) res.push_back(i);
            for (int i = l1; i <= r1; i++) res.push_back(i);
        } else {
            // 区间重叠，合并为一个连续区间
            int L = min(l1, l2);
            int R = max(r1, r2);
            for (int i = L; i <= R; i++) res.push_back(i);
        }
        
        cout << res.size() << '\n';
        for (int i = 0; i < (int)res.size(); i++) {
            cout << res[i] << " \n"[i == (int)res.size() - 1];
        }
    }
    
    return 0;
}

关键点总结

1. 区间连续性：由 $\pm 1$ 组成的子段和构成连续区间
2. 前缀和技巧：$[l, r]$ 的和 = $pref[r+1] - pref[l]$
3. 分类讨论：分含特殊元素和不含特殊元素两类
4. 边界处理：空子段保证 $0$ 一定在结果中
5. 区间合并：两个连续区间的并集最多两个区间