最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

本题大致意思就是给定一个数组

然后让我们统计这个数组有多少个乘积是正数的子区间和乘积是负数的子区间

题解一（前缀和维护区间负数个数）

看到求区间的问题，会想到前缀和优化

我们可以用前缀和数组维护 $[1,s_i]$ 区间内的负数个数(因为会影响乘积的正负号的只有负数)

则对于区间 $[s_l,s_r] = v$，若 $v$ 是奇数，则表示该区间的乘积为负数，反之是正数

若$s_r - s_{l-1}$为奇数(即区间乘积为负数)，则必定是 $s_r$ 和 $s_{l-1}$ 一奇一偶

若$s_r - s_{l-1}$为偶数(即区间乘积为正数)，则必定是 $s_r$ 和 $s_{l-1}$ 都是偶数或都是奇数

于是我们可以从前往后遍历一遍数组，求出前缀和分别为奇数和偶数的个数

然后是一个组合数的问题了，设前缀和为奇数的个数为$v_1$，前缀和为偶数的个数为$v_2$

区间乘积为负数的子区间个数为 $C_{v_1}^1 \times C_{v_2}^1$

区间乘积为正数的子区间个数为 $C_{v_1}^2 + C_{v_2}^2$

Code

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

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;
int n;
int s[N];
int s0, s1; //s0统计前缀和为偶数的个数，s1统计前缀和为奇数的个数

int main()
{
    cin >> n;
    s0 ++ ; //s[0]是偶数，直接加进去，省掉额外迭代一轮的操作
    for (int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;

        s[i] = s[i - 1] + (x < 0);

        if (s[i] & 1) ++ s1;
        else ++ s0;
    }
    cout << (LL)s0 * s1 << " " << (LL)s0 * (s0 - 1) / 2 + (LL)s1 * (s1 - 1) / 2 << endl;
    return 0;
}

省掉一维空间复杂度的写法(受墨染空大佬代码的启发)

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

using namespace std;

typedef long long LL;

int n, v, x;    //v=0代表前缀偶数个负数，v=1奇数个负数
int s[2];
LL r1, r2;

int main()
{
    cin >> n;
    s[0] ++ ;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> x;
        if (x < 0) v ^= 1;  //改变前缀负数个数的奇偶型
        r1 += s[v ^ 1]; //负数区间端点一奇一偶
        r2 += s[v];     //正数区间端点同奇同偶
        s[v & 1] ++ ;
    }
    cout << r1 << " " << r2 << endl;
    return 0;
}

题解二（用前缀和模拟前缀积的解法）

顾名思义，我们可以用一个前缀积数组，来判断一个区间 $[s_l,s_r]$ 的乘积的正负数

同样我们不需要完全模拟出前缀的乘积，也只需维护正负号的数量关系，原因同之前一样

于是我们可以规定区间：

1. $[1,s_i] = ~~~1$ 表示该段前缀区间的乘积为正数

2. $[1,s_i] = -1$ 表示该段前缀区间的乘积为负数

然后我们就可以枚举区间的右端点 $s_r$，寻找合法的左端点了 $s_l$

$区间积为负数 \Leftrightarrow [s_l, s_r] < 0 \Leftrightarrow s_r \div s_{l-1} = -1$

$区间积为正数 \Leftrightarrow [s_l, s_r] > 0 \Leftrightarrow s_r \div s_{l-1} = ~~~1$

因此，我们从前往后枚举右端点的时候，还需要额外记录前缀积为正数和负数的个数，也就是对于当前右端点来说，合法的左端点个数。

把这些区间个数相加，就是最终答案了

Code

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, x;
int s[N];
int lpos, lneg;
LL r1, r2;

int main()
{
    lpos = s[0] = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &x);
        if (x > 0) x = 1;
        else x = -1;

        s[i] = s[i - 1] * x;

        //r > 0
        if (s[i] > 0)
        {
            r1 += lpos; //正区间积个数 => l>0
            r2 += lneg; //负区间积个数 => l<0
            lpos ++ ;   //对于之后的右端点来说，当前点就变成了左端点啦
        }
        //r < 0
        else
        {
            r1 += lneg; //正区间积个数 => l<0
            r2 += lpos; //负区间积个数 => l>0
            lneg ++ ;
        }
    }
    printf("%lld %lld\n", r2, r1);
    return 0;
}

省掉一维空间复杂度的写法

#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;
}