思路

我们通过前缀积来求解。我们$val$表示前缀积，$ne$和$po$分别表示所有前缀积中负数和正数的个数，$ans1$和$ans2$记录答案。假如我们枚举到$i$，此时$val$大于$0$，那么表示$[1,i]$的数组乘积为正，此时由于我们知道$po$和$ne$，由于正数除正数是正数，正数除负数是负数可以知道，有几个$po$就可以有几个$[k,i]$数组乘积为正（$k$是前缀积为正时对应的下标（$K<=i$）），反之$ne$可以知$[k,i]$乘积为负，除此以外，正数的个数还要加1，原因是$[1,i]$也是正数。负数也类似的讨论

python代码

n = int(input())
arr = list(map(int, input().split()))
val, ne, po, ans1, ans2 = 1, 0, 0, 0, 0
for i in range(n):
    val = val * (1 if arr[i] > 0 else -1)
    if val > 0:
        ans1 += ne
        ans2 += po + 1
    else:
        ans1 += po + 1
        ans2 += ne
    if val > 0:
        po += 1
    else:
        ne += 1
print(ans1, ans2)
# 5
# 5 -3 3 -1 1

C++代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
int n;
int arr[MAXN];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> arr[i];
	int val = 1;
	int ne = 0, po = 0;
	ll ans1 = 0, ans2 = 0;
	for(int i = 1; i <= n; i++){
		val *= arr[i] >= 0? 1 : -1;
		if(val > 0){
			ans1 += ne;
			ans2 += po + 1;
			po++;
		}else{
			ans1 += po + 1;
			ans2 += ne;
			ne++;
		}
	}
	cout << ans1 << " " << ans2 << endl;
}

// 5
// 5 -3 3 -1 1

题目内容

在一个神奇的世界里，魔法元素是非常重要的，它们有着巨大的能量。魔法师小红也是这个世界的一名著名的魔法师，他掌握了许多神奇的魔法。但他总是想知道，使用他所拥有的魔法元素，是否有足够的能量施展出一种强大的魔法。

于是，他将所有魔法元素排成一行，从左到右第 $i$ 个魔法元素的能量值是一个非零整数 $a_i$ 。他发现，他可以选出一段连续的魔法元素，将它们的能量值乘起来得到一个总能量值。如果这个总能量值大于零，他就能施展出一种白魔法，否则他只能施展出黑魔法。

现在小红想知道施展一个白魔法或黑魔法的方案数分别有多少。两个方案不同是指挑选的连续区间不同。

输入描述

第一行有一个整数 $n$ ( $1\le n \le 2\times 10^5$ )，表示魔法元素的个数。

第二行有 $n$ 个整数 $a_1,a_2,...,a_n$ ( $-10^9 \le a_i \le 10^9$ )，代表魔法元素的能量值。

输出描述

输出两个整数，分别表示施展一个黑魔法和施展一个白魔法的方案数。

样例

输入

6
6 -1 -3 5 3 -5

输出

10 11