算法1 前缀和+一维dp

由于只考虑正负，我们把整数都记为1，负数都记为-1（免得求前缀积的时候爆了）
求一下前缀积，这时候可以把问题转换为在n个数里面求有几对数字，乘积为正，假设为k
一共有$sum = C_n^2 + n$种方法，那么乘积为负的对数为sum-k
我们设res或者dp[i]也行，为前i个数中有几对数字乘积为正
假如当前数字为正，则加上之前为正的个数；假如当前数字为负，加上之前为负的个数
计算完成后，记录前i个数字中pre[i]为正和负的个数即可

时间复杂度$O(n)$

C++ 代码

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int pre[N];//前缀积
int cnt[3];//记录当前，前i个数中有几个为负数，几个为整数
int main()
{
    ll n;
    cin >> n;
    pre[0] = 1;//0处设为正，保证结果是对的
    for (int i = 1;i<=n;i++)
    {
        int x;
        cin >> x;
        if(x>0)
            x = 1;
        else
            x = -1;
        pre[i] = pre[i - 1] * x;
    }
    cnt[2] = 1;//pre[0]为正的，所以先把正的设为1，这样1~i的结果就不会漏掉了
    ll res = 0;
    for (int i = 1;i<=n;i++)
    {
        if(pre[i]==1)
            res += cnt[2];
        else
            res += cnt[0];
        cnt[pre[i] + 1]++;
    }
    ll total = n * (n - 1) / 2 + n;
    cout << total - res << ' '<< res;
}