题目描述

给定一个长度为 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。

C++ 代码

#include<iostream>
#include<vector>
using namespace std;
//只需要统计前缀和中1或者0的数量
//1表示正数
//0表示负数
//如果前缀和数组arr[i]==arr[j]就算一组正索引[l,r]
//所以如果前缀和正数的数量为one 那么可以有(one+1)*one/2组正索引
//前缀和负数的数量为fuone 那么可以有(fuone-1)*fuone/2组正索引
//剩余其他的都属于负索引
int main()
{
    long n;
    cin>>n;
    long one = 0;
    long res1,res2;
    int num,pre = 1;
    while(cin>>num)
    {
        num = num>0?1:0;
        one+=(num==pre);//统计前缀和正数的数量
        pre =(num==pre);
    }
    long fuone = n - one;//前缀和负数的数量
    res1 = (one+1)*one/2 + (fuone-1)*fuone/2;
    res2 = (n+1)*n/2 - res1;
    cout<<res2<<" "<<res1;
    return 0;
}