B. The Number of Products
链接：https://codeforces.com/contest/1215/problem/B
You are provided with an ordered collection a_1, a_2, \dots, a_n composed of n non-zero integer elements (where each element satisfies a_i \neq 0).
You have to calculate two following values:
the count of index pairs (l, r) where l \leq r and the product a_l \cdot a_{l+1} \dotsm a_{r-1} \cdot a_r is negative;
Input
The first line contains an integer nn (where 1 ≤ n ≤ 2 × 10⁵) — representing the total number of elements in the sequence.
The second line consists of n squared integer values a₁, a₂, …, aₙ (where each ai satisfies −10⁹ ≤ ai ≤ 10⁹ and ai ≠ 0) — the elements of the sequence.
Output
Output two integers: the count of subsegments that have a negative product and the count of those that have a positive product.
Examples
input
Copy
output
Copy
input
Copy
output
Copy
input
Copy
output
Copy
思路：
该算法基于O(n)时间复杂度设计，在处理数据序列时需要对结果进行精度保留以避免溢出问题。具体而言，在遍历数据序列的过程中需要统计可形成的最大正值和最小值的数量，并分别在s1和s2中累积统计数量。当处理到一个正数值时，则继承上一个状态并增加当前的正数值计数值。对于出现的负值，则需要交换当前的正、负数值计数值，并增加对应的相应计数值。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;
long long n,s1=0,s2=0,a1=0,a2=0,c;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x>0)
{
a1++;
}
else
{
c=a2;
a2=a1;
a1=c;
a2++;
}
s1+=a1;
s2+=a2;
}
printf("%lld %lld",s2,s1);
}