本文共 1541 字，大约阅读时间需要 5 分钟。

这道题主要有两种做法，一种是递推，另一种是前缀和，然后用组合数学算。

方法一：递推

我们先求假设前n项前缀积为s[n]。那么我要要求一个区间[ l, r ]的所有数乘积就是s[r] / s[l-1]。如果[ l, r ]的所有数乘积为正，则s[r]和s[l-1]同号为负则异号。那么我们只要遍历一遍，维护s[r]（即前r个数的前缀积）和前面有多少个前缀积为正数、负数。然后根据sum[r]的情况来用前面有多少个前缀积为正、负来计算答案。

同时因为只考虑正负即可，所以只需要把正数当成1，负数当成-1。

方法二：前缀和加组合数学

这种方法是先统计出前面有多少个前缀积为负的情况（记为sum1）和多少个前缀积为正(记为sum2)的情况。

那么对于积为正的区间，我们只需要选取两个前缀和为正的点（sum[r]/sum[l-1]）,也就是选出l，r，或者选出两个前缀和为负的点，负负得正。sump=C_{sum1}^{2}+C_{sum2}^{2} sump=C_{sum1}^{2}+C_{sum2}^{2}。

对于积为负的区间，我们只需要选一个负的和一个正的即可 sumn=C_{sum1}^{1}∗C_{sum2}^{1}。

该方法通过统计前缀积为正和负的数量，然后根据组合数学知识，计算满足条件的区间数。

最终答案

给定一个长度为 n 且不包含 0 的整数序列 a1,a2,…,an，请计算以下两值：使得al×al+1×…×ar 为负的索引对 (l,r)(l≤r) 的数量 和 使得al×al+1×…×ar 为正的索引对 (l,r)(l≤r) 的数量。

输入格式

第一行一个整数 n。第二行包含 n 个整数 a1,…,an。

输出格式

共一行，输出单个空格隔开的两个整数，分别表示负的索引对数和正的索引对数。比如输入样例1 5 5 -3 3 -1 1 输出样例1 8 7。

解决代码

using namespace std;int main() {    int n;    scanf("%d", &n);    vector
   
     prefix(n + 1, 1);    for(int i=1; i<=n; ++i) {        long long x;        scanf("%d", &x);        if(x <0) prefix[i] *= -1;    }    long long pos =0, neg=0, ans1=0, ans2=0;    for(int i=0; i<=n; ++i) {        if((i ==0) || (prefix[i] >0)) {            pos++;        } else {            neg++;        }    }    for(int i=0; i<=n; ++i) {        if((i==0) || (prefix[i]>0)) {            ans2 += pos;        }        if((i==0) || (prefix[i] ==1)) {            ans1 += pos;        }        if((i==0) || ((prefix[i]) <0)) {            ans2 += neg;        }        if(((prefix[i]) <0)) {            ans1 += neg;        }    }    printf("%lld %lld", ans1, ans2);    return 0;}