题目链接: CF585. 乘积数量

题目描述

给定一个长度为 n 且不包含 0 的整数序列 $a_1,a_2,…,a_n$。

请你计算以下两值：

1. 使得 $a_l×a_{l+1}×…×a_r$ 为负的索引对 (l,r)且(l≤r)的数量。
2. 使得 $a_l×a_{l+1}×…×a_r$ 为正的索引对 (l,r)且(l≤r)的数量。

输入格式

第一行一个整数 n。

第二行包含 n 个整数 $a1,…,an$.

输出格式

共一行，输出单个空格隔开的两个整数，分别表示负的索引对数和正的索引对数。

数据范围

$1 ≤ n ≤ 2×10^5$
$−10^9≤ a_i ≤ 10^9,a_i≠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

思路分析

首先分析题目我们看到, 需要计算$a_l×a_{l+1}×…×a_r$这段区间乘积的正负情况, 快速计算出一段区间内的运算结果, 我们可以很快地想到前缀和的思想, 这里当然并不是算和, 但是我们同样可以用这个思想预处理出一段区间的乘积是多少, 这样我们就可以用$O(1)$ 的时间快速得到一段区间的乘积, 而且由于只需要判断区间的乘积情况, 故我们并不需要真的存下具体的$a_i$,只需要存下其正负号即可. 这样处理之后得到一个数组s, s[i] 的含义为 $a_1 \times a_2 \times a_3 .... \times ai$ 的正负情况, 如果我们想知道一段区间的正负情况, 例如想知道区间(l, r) 乘积的正负情况, 即得到 $a_l×a_{l+1}×…×a_r$ 的正负情况, 用我们的s数组表示则为 $\frac{s[r]}{s[l - 1]}$ , 其中 1 $\le$ l $\le$ r, 那么以$a_r$为右端点的区间个数中, 其区间乘积结果的正负取决于$s[l - 1]$与$s[r]$ 的正负情况, 若两者符号同号, 则这段区间的乘积结果为正数, 若两者符号相反, 则这段区间的乘积结果为负数. 故以$a_r$为右端点且乘积为正数的区间的个数等于s[l - 1] (1 $\le$ l $\le$ r) 中, 即s[$0$ ~ $r - 1$]中和s[r]符号相同的个数, 同理乘积为负数的区间个数等于与s[r]符号相反的元素个数. 故我们只要遍历所有的$a_i$(从$a_1$ ~ $a_n$),计算出以$a_i$为右端点的情况,即可得到所有的区间情况，故接下来具体看代码实现, 如何实现上面的过程.

C++ 代码1

#include<iostream>
using namespace std;
constexpr int N = 2 * 1e+5 + 10;
int s[N];              // 前缀和数组

auto main() -> int
{
    ios::sync_with_stdio(false); 
    int n; cin >> n;    
    s[0] = 1;         // 前缀s[0] 预处理为1 

    //res1 表示乘积为正数的区间个数, res2 表示乘积为负数的区间个数
    // j 表示目前s[0 ~ i - 1]中符号为正的个数, k 表示目前s[0 ~ i - 1]中符号为负的个数
    // 由于s[0] = 1, 故目前 j = 1, k = 0, 由于数据会爆int, 故这里用long long
    long long res1 = 0, res2 = 0, j = 1, k = 0;   

    for(int i = 1; i <= n; ++i)    // 从a1 ~ an 遍历, 边输入边处理
    {
        int flag = 1;              
        int a; cin >> a; 
        if(a < 0) flag = -1;      // 若本次的遍历的值为负, 则乘积结果为s[i - 1] 的相反数
        s[i] = s[i - 1] * flag;   

        // 若s[i]为正数, 则乘积为正的区间个数为s[0 ~ i - 1]中符号为正的个数,即为j目前的个数. 
        // 乘积为负的区间个数为s[0 ~ i - 1]中符号为负的个数, 即为k, 最后由于s[i]是正数,故++j,负数情况同样分析
        if(s[i] > 0) res1 += j, res2 += k, ++j;   
        else res1 += k, res2 += j, ++k; 
    }

    cout << res2 << " " << res1 << endl; 
    return 0;
}

C++ 代码2 改进

由于我们实际计算的过程中并不需要用一个数组存下之前的所有s[$i$ ~ $n - 1$] 的情况, 我们计算一个s[i]的时候只需要知道s[$i - 1$]的正负情况即可, 故这里我们可以不需要这个数组, 直接用一个pre变量表示s[i - 1]即可. 剩下的情况分析,与上面相同, 由于我们这个算法只需遍历一遍我们的序列即可, 故其时间复杂度为$O(n)$.

#include<iostream>
using namespace std;
constexpr int N = 2 * 1e+5 + 10;

auto main() -> int
{
    ios::sync_with_stdio(false); 
    int n; cin >> n;    

    long long res1 = 0, res2 = 0, j = 1, k = 0, pre = 1;  

    for(int i = 1; i <= n; ++i)
    {
        int a; cin >> a; 
        if(a < 0) pre *= -1; 

        if(pre > 0) res1 += j, res2 += k, ++j;
        else res1 += k, res2 += j, ++k; 
    }

    cout << res2 << " " << res1 << endl; 
    return 0;
}

时间复杂度 $O(n)$