题目描述

*题目给定一个数组，将其分为一段一段的，
找出有多少个区间段中各个数字的乘积为正号以及多少个乘积为负号。*

样例

5
5 -3 3 -1 1

前缀和 时间复杂度$O(n)$

区间问题考虑用前缀和优化。
举例在 S[l]~S[r] 之间要找出所有的乘积为正的区间数量，通过前缀和，得到从 S[0] ~ S[r] 的乘积，
那么如果想要判断 S[l]~S[r] 这个区间的乘积的正负，只要将S[0]~S[r] 这个区间来除以 S[l-1] 即可得到正负情况。

那么按照顺序求取S[l]~S[r]之间所有以S[r]为终点的区间情况，
则 将S[0]~S[r] 该区间分别除以 S[l-1], S[l], S[l+1]…S[r] 得到各个区间的正负情况。
S[l-1]~S[r] 只要记录出有多少个与 S[r] 同号 或者 异号，那么就可以求出当前各个子区间正负.

于是，我们可以以 S[i] 为终点进行遍历，计算从 S[0]~S[i] 中各个正负子区间的数量。
维护两个变量 sp 和 np 分别表示从S[0]~S[i] 中有多少个是正号，有多少个是负号
而rp 和 rn 则表示以 S[i] 为终点有多少个正号子区间 及 负号子区间。

同时，因为我们只需要求取正负的数量，而无需关注数组的数值大小，我们可以只判断正负，不用计算数值。
用一个变量 s 表示从S[0]到当前判断的值的前缀和的正负情况。

Java 代码

import java.util.Scanner;

public class Acwing_3574 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long rp = 0,rn = 0;
        int sp = 1, sn = 0, s = 1;   //自身相乘定为正数，所以sp初始为1，s维护前缀和
        while((n--) != 0) {
            int a = sc.nextInt();
            if(a < 0) s *= -1;       //只有为负号的情况下，s才改变
            if(s > 0) {
                rp += sp;           //当前缀和为正数，正号子区间加上前项同为为正的个数，
                rn += sn;           //负号子区间加上前项为负的个数
                sp++;               //前项为正个数加1
            }else {
                rp += sn;           //当前缀为负数，正号子区间加上前项同为负的个数
                rn += sp;           //负号子区间加上前项为正的个数
                sn++;
            }
        }
        System.out.print(rn + " " + rp);
    }
}