题目描述(CF1215B)
给定一个长度为 n 且不包含 0 的整数序列 a1,a2,…,an。
请你计算以下两值:
- 使得 al×al+1×…×ar 为负的索引对 (l,r)(l≤r) 的数量。
- 使得 al×al+1×…×ar 为正的索引对 (l,r)(l≤r) 的数量。
样例
输入样例
10
4 2 -4 3 1 2 -4 3 2 3
输出样例
28 27
数据范围
1≤n≤2×105 ,
−10^9≤ai≤10^9,ai≠0。
解题思路
$O(n)$
- 看见区间问题直接一个前缀和;
- 在此题中,为了一次遍历即可得出结果,多记录了当前元素左边的正前缀积和负前缀积,以及每一个当前元素时的正负结果;
#include<iostream>
using namespace std;
int main()
{
int n;
long long resP = 0, resN = 0; //resP表示当前正索引数量, resN表示当前负索引数量;
int sp = 1, sn = 0, s = 1, a; //sp是前缀多少正数,sn是前缀多少负数,s是当前前缀和;
cin>>n;
while(n--){
cin>>a;
if(a < 0) s *= -1;
if(s > 0) {resP += sp; resN += sn; ++sp;}
else {resP += sn; resN += sp; ++sn;}
}
cout<<resN<<' '<<resP<<endl;
}