题目描述

难度分:$1400$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9,a[i]≠0)$。
输出两个数：

1. 有多少个非空连续子数组，乘积是负数？
2. 有多少个非空连续子数组，乘积是正数？

输入样例$1$

5
5 -3 3 -1 1

输出样例$1$

8 7

输入样例$2$

10
4 2 -4 3 1 2 -4 3 2 3

输出样例$2$

28 27

输入样例$3$

5
-1 -2 -3 -4 -5

输出样例$3$

9 6

算法

前缀和

本题中没有$a[i]=0$的情况，还是很容易分析的。只要子数组中负数的个数是奇数，其乘积结果就是负数。开辟一个数组$cnt_{1 \times 2}$，其中$cnt[0]$表示数组$a$的前缀$[1,i)$中负数出现次数为偶数的次数，$cnt[1]$表示数组$a$的前缀$[1,i)$中负数出现次数为奇数的次数。

然后从左往右遍历$i \in [1,n]$，当遍历到$a[i]$时，维护一个前缀$[1,i]$中负数的个数$presum$：

1. 如果$presum$为奇数，就考察前面所有位置$j \in i$中，前缀$[1,j]$中负数个数为偶数的次数$cnt[0]$，满足这个条件的所有$j$，都会有子数组$(j,i]$中有奇数个负数，把$cnt[0]$累加到答案上即可。而由于此时$presum$是奇数，所以$cnt[1]$自增。
2. 同理分析$presum$为偶数的情况就行了。

按照以上的算法流程就能计算出乘积结果为负数的子数组数量，而$a$总共的子数组数量为$\frac{n \times (n+1)}{2}$，用它减去乘积结果为负数的子数组数量就能得到乘积结果为偶数的子数组数量。

复杂度分析

时间复杂度

只遍历了一遍数组$a$，时间复杂度为$O(n)$。

空间复杂度

尽管开辟了一个数组用于记录前缀中负数数量偶数或奇数次的频数，但这个数组的大小恒定为$2$，与数据量$n$没有关系，所以总的变量数也就是有限几个，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

int main() {
    int n;
    scanf("%d", &n);
    int cnt[2] = {0};
    cnt[0] = 1;
    int presum = 0;
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if(x < 0) presum++;
        if(presum&1) {
            ans += cnt[0];
            cnt[1]++;
        }else {
            ans += cnt[1];
            cnt[0]++;
        }
    }
    printf("%lld %lld\n", ans, (LL)n*(n + 1)/2 - ans);
    return 0;
}