题目描述

给定一个长度为 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≤n≤2×105,
−109≤ai≤109,ai≠0。

输入样例

5
5 -3 3 -1 1

输出样例

8 7

变量含义

po：结果正的索引对的总个数
pl：结果为负的索引对的总个数

spo：代表本次以i为右端点时，比以i-1为右端点时正索引数量的增量
spl：代表本次以i为右端点时，比以i-1为右端点时负索引数量的增量

主要解题思路

从左向右依次遍历数组，
当a[i] 为正，也即右端点为正时，则正索引数量至少增加一 po++ ，而又因为加入的正数对上一轮的结果没影响，所以以i-1为右端点的正索引数的增量与本轮相同，也即
po += spo.所以本轮po = po + 1+ spo; po的增量 spo = 1+ spo. pl的增量与上一轮相同，
则pl = pl + spl

当a[i] 为负的时候，负索引数量至少增加1, pl ++, 而又因为当前加入的数为负数所以，先前为正的结果乘上当前值都会变成负值，先前为负的结果乘上当前值都会变成正值。也即当前 pl = pl +1 +spo ,负索引增量spl = 1+spo ; 正索引数量po = po + spl ， 增量spo = spl。

C++ 代码

#include<iostream>


using namespace std;

const int N = 200010;

long long  a[N], p[N];
long long  s[N];
int n;
int main()
{
    cin >> n;
    scanf("%lld" , &a[1]);
    long long po = 0;
    long long pl = 0;
    int spo = 0,spl  = 0;

    if( a[1] > 0) spo = 1 ,po =1;
    else spl  =1 ,pl = 1;

    for(int i = 2 ; i<= n ; i++)
    {
        scanf("%lld",&a[i]);
        if( a[i] > 0)
        {
            po++;
            po = po + spo;

            pl = pl + spl;

            int k = spo;
            spo++;
        }else
        {
            pl ++ ;
            pl = pl + spo;

            po = po + spl;

            int k = spl;

            spl = 1+ spo;
            spo = k;

        }
    }

    cout << pl <<' ' <<po;
    return 0;

}