题目描述省略

算法1

(DP) $O(n)$

设数组为a[N]，枚举以每个数为终点，f为以当前数为终点的所有索引对乘积为正的区间数量，g为以当前数为终点的索引对 乘积为负的区间数量。(设当前数为i，所有区间即为(0, i), (1, i)……(i, i))。

当a[i]为正时，可以发现集合可以划分成以a[i]为终点，长度为1的区间和长度大于1的区间。
对于f：前者的值为1；后者的值即为以a[i - 1]为结尾，所有索引对乘积为正的区间数量，即为f[i - 1]；
对于g：前者的值为0；后者为g[i - 1]。
转移方程为f[i] = 1 + f[i - 1], g[i] = g[i - 1]。

当a[i]为负时，同上。
对于f：前者的值为0；后者的值即为以a[i - 1]为结尾，所有索引对乘积为负的区间数量，即为g[i - 1]；
对于g：前者的值为1；后者为f[i - 1]。
转移方程为f[i] = g[i - 1], g[i] = 1 + f[i - 1]。

因为每次转移只与上一次状态有关，所以可以优化空间为常数。

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n;
LL f, g;

int main()
{
    scanf("%d", &n);

    LL res1 = 0, res2 = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int a;
        scanf("%d", &a);
        if(a > 0) f ++;
        else
        {
            int tmp = f;
            f = g;
            g = 1 + tmp;
        }
        res1 += f, res2 += g;
    }

    printf("%lld %lld\n", res2, res1);
    return 0;
}