AcWing 3574. 乘积数量
原题链接
中等
作者:
sowei
,
2021-05-27 12:02:50
,
所有人可见
,
阅读 197
import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long rp = 0, rn = 0; //rp是使得 al×al+1×…×ar 为负的索引对 (l,r)(l≤r) 的数量, rn是使得 al×al+1×…×ar 为正的索引对 (l,r)(l≤r) 的数量
int sp = 1, sn = 0, s = 1; //s = 1 意思是s[0] = 1, sp是当前有几个正数,sn是当前有几个负数
while(n-- > 0) {
int num = sc.nextInt();
if(num < 0) s *= -1; //前缀积, 只存正负号,不存实际的乘积
if(s > 0) {
rp += sp; rn += sn; sp++;
} else {
rp += sn; rn += sp; sn++;
}
}
System.out.println(rn + " " + rp);
}
}