题目大意

给定一个长度为 $n$ 的非零整数序列 $a_1, a_2, \dots, a_n$，求有多少个子段（连续子数组）的乘积为正，多少个子段的乘积为负。

解题思路

乘积的符号只取决于子段中负数的个数：

• 偶数个负数 → 乘积为正；
• 奇数个负数 → 乘积为负。

因此问题转化为：统计所有子段中，负数个数为偶数的子段数（正乘积）和负数个数为奇数的子段数（负乘积）。

前缀和思想

设 $pref[i]$ 表示前 $i$ 个元素中负数的个数（即从 $1$ 到 $i$ 的负数个数）。对于子段 $(l, r)$，其负数的个数为 $pref[r] - pref[l-1]$。
子段乘积为正当且仅当 $pref[r] - pref[l-1]$ 是偶数，即 $pref[r]$ 与 $pref[l-1]$ 的奇偶性相同。
同理，乘积为负当且仅当奇偶性不同。

因此，我们只需要统计所有前缀负数的奇偶性，然后：

• 正乘积子段数 = 所有奇偶相同的前缀对 $(l-1, r)$ 的数量（其中 $0 \le l-1 < r \le n$）。
• 负乘积子段数 = 所有奇偶不同的前缀对的数量。

线性扫描算法

我们可以一边遍历数组，一边维护：

• bal：当前前缀中负数的个数（实际上只关心奇偶性，可以用 $0/1$ 表示）。
• cnt[0]：之前出现过的前缀中，负数个数为偶数的位置数量（包括空前缀 $pref[0]=0$）。
• cnt[1]：之前出现过的前缀中，负数个数为奇数的位置数量。

初始化：$cnt[0] = 1$（空前缀，负数个数为 $0$，偶数），$cnt[1] = 0$，$bal = 0$。

遍历 $i = 1$ 到 $n$：

1. 如果 $a_i < 0$，则 $bal = 1 - bal$（奇偶翻转）。
2. 此时，以 $i$ 结尾的子段中，乘积为正的子段数等于所有前缀 $pref[j]$（$0 \le j \le i-1$）中与当前 $bal$ 奇偶相同的个数，即 $cnt[bal]$。因为子段 $(j+1, i)$ 的负数个数 = $bal - pref[j]$，奇偶相同则差为偶数。
3. 将 $cnt[bal]$ 累加到答案 pos 中。
4. 更新 $cnt[bal] = cnt[bal] + 1$（将当前前缀 $pref[i]$ 加入统计）。

遍历结束后，pos 即为正乘积子段总数。
总子段数为 $total = \frac{n \cdot (n+1)}{2}$，负乘积子段数为 $total - pos$。

时间复杂度

$O(n)$，空间 $O(1)$，完全满足 $n \le 2 \times 10^5$。

示例验证

以第一个样例：5 -3 3 -1 1

• 初始化：$cnt[0]=1, cnt[1]=0, bal=0, pos=0$
• i=1, a=5>0, bal=0, 加 cnt[0]=1 → pos=1, cnt[0]=2
• i=2, a=-3<0, bal=1, 加 cnt[1]=0 → pos=1, cnt[1]=1
• i=3, a=3>0, bal=1, 加 cnt[1]=1 → pos=2, cnt[1]=2
• i=4, a=-1<0, bal=0, 加 cnt[0]=2 → pos=4, cnt[0]=3
• i=5, a=1>0, bal=0, 加 cnt[0]=3 → pos=7
  总子段数 $= 5*6/2=15$，负乘积 $=15-7=8$。输出 8 7，正确。

代码实现（C++）

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

int main() {
    int n;
    cin >> n;
    long long pos = 0;  // 正乘积子段数
    int cnt[2] = {1, 0}; // cnt[0]偶数，cnt[1]奇数，初始空前缀偶数
    int bal = 0;         // 当前前缀负数个数的奇偶性（0偶1奇）
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x < 0) bal ^= 1;      // 遇到负数，奇偶翻转
        pos += cnt[bal];          // 累加以i结尾的正乘积子段数
        cnt[bal]++;               // 当前前缀加入统计
    }
    long long total = 1LL * n * (n + 1) / 2;
    cout << total - pos << " " << pos << endl;
    return 0;
}

总结

本题的关键在于将乘积符号问题转化为前缀负数个数的奇偶性统计，利用前缀和与计数数组在 $O(n)$ 时间内完成计算。注意空前缀的初始处理，以及使用 long long 避免溢出。