题目描述

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

样例

输入样例1：
5
5 -3 3 -1 1
输出样例1：
8 7
输入样例2：
10
4 2 -4 3 1 2 -4 3 2 3
输出样例2：
28 27
输入样例3：
5
-1 -2 -3 -4 -5
输出样例3：
9 6

算法1

(dp) $O(n)$

时间复杂度

参考文献

一开始自己写的很麻烦

python3 代码

n = int(input())
nums = []
for x in input().split():
    if int(x) > 0:
        nums.append(1)
    else:
        nums.append(-1)

dp1 = [0 for _ in range(n + 1)]     #负数
dp2 = [0 for _ in range(n + 1)]     #正数

for i in range(1, n + 1):
    if nums[i-1] == -1:
        dp1[i] = 1
        dp1[i] += dp2[i-1]
        dp2[i] += dp1[i-1]
    else:
        dp2[i] = 1
        dp1[i] += dp1[i-1]
        dp2[i] += dp2[i-1]

res1 = sum(dp1)
res2 = sum(dp2)

print("{} {}".format(res1, res2))

看了y总讲解后，优化了很多。没必要开那么多的空间

python3 代码

n = int(input())

curmul = 1
pre_negative = 0
pre_positive = 1
res_negative = 0
res_positive = 0

for x in input().split():
    if int(x) < 0:
        curmul *= -1
    if curmul < 0:
        res_negative += pre_positive
        res_positive += pre_negative
        pre_negative += 1
    else:
        res_negative += pre_negative
        res_positive += pre_positive
        pre_positive += 1

print(res_negative, res_positive)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;  cin >> n;
    long long t;
    int curmul = 1;
    long long pre_negative = 0,   pre_positive = 1;
    long long res_negative = 0,   res_positive = 0;
    while(n --)
    {
        cin >> t;
        if (t < 0)
            curmul *= -1;
        if (curmul < 0)
        {
            res_negative += pre_positive;
            res_positive += pre_negative;
            pre_negative ++;
        }
        else
        {
            res_negative += pre_negative;
            res_positive += pre_positive;
            pre_positive ++;
        }
    }

    cout << res_negative << ' ' << res_positive << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla