题目描述

给定n个数，找有多少个连续的区间乘积为正和负。
虽然题目是用前缀和来写，但是推起来并不是那么简单的

a1a2a3a4…an
求有多少个类似于连续
ai ai+1....aj 个数的乘积为正和负。

解法：

可以想到用前缀和来写，用一组数据来保存从1到i的乘积为正和负，
但是那样还是会超时，
这时应该观察复杂度，应该小于nlogn，
看一下ai ai+1....aj从j往前看，
从aj-1，到aj 判断式子为 s[j]/s[j-2];
依次类推
从aj-2，到aj 判断式子为 s[j]/s[j-3];
从aj-3，到aj 判断式子为 s[j]/s[j-4];
从aj-4，到aj 判断式子为 s[j]/s[j-5];

他们的s[j]相同，那么只需要计算s[j-i]的正负数量就可以了，时间复杂度为O(n);
我们只需要存s[i]中正负数的数量就可以了。

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, cur, x;
int lpos, lneg;
LL r1, r2;

int main()
{
    lpos = cur = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &x);
        if (x < 0) cur *= -1;
        if (cur > 0) r1 += lpos, r2 += lneg, lpos ++ ;
        else r1 += lneg, r2 += lpos, lneg ++ ;
    }
    printf("%lld %lld\n", r2, r1);
    return 0;
}