The Number of Products(线性统计区间个数)
The sequence composed of aa₁, aa₂,…,aaₙ is made up of nn non-zero integers (for example, each aa_i ≠ 0).
You have to calculate two following values:
the count of index pairs (l, r), where l ≤ r, satisfying their product being negative;
the count of index pairs (l, r), where l ≤ r, satisfying their product being negative;
Input
The first line includes one integer nn (where 1≤n≤2⋅105)(where 1≤n≤2⋅105) — representing the quantity of elements in the sequence.
The second line includes nn integers a₁,a₂,…,aₙ (−10⁹ ≤ aᵢ ≤ 1₀⁹;aᵢ ≠ 0) — the elements of the sequence.
Output
Print out two integers — the count of subarrays with a negative product and the count of subarrays with a positive product.
Examples
input
Copy
5
5 -3 3 -1 1output
Copy
8 7input
Copy
10
4 2 -4 3 1 2 -4 3 2 3output
Copy
28 27input
Copy
5
-1 -2 -3 -4 -5output
Copy
9 6题意：给定任意整数n，请构造一个包含n个元素且长度正好为n的一维数组。我们定义数组中任意连续一段数字（至少有一个元素）其乘积小于零的情况称为"负区间"；乘积大于零的情况称为"正区间"；特别地，在这种情况下每个单独元素都算作是一个独立的小于一元组合而成的大于零的结果被视为单独情况下的对应情况）。请计算上述序列中所包含的所有'负'与'正'区间的总数量。
思路：总的区间数量等于从1加到n的和即n*(n+1)/2；由于累积相乘的关系，在每个区域内加入任意一个正数值都不会影响该区域本身的性质；而区域的具体属性主要取决于其中包含的负数值数量（若其数量为奇，则属于负区域；若偶则属于正区域）。因此为了确定所有正区域的数量只需先计算出所有包含至少一个负值的区域数目，并将其从总数中减去即可得到最终结果
具体步骤如下：
1、让数组的0号位置记为1；
按顺序输入n个数值。若当前输入的数值为正，则该位置对应的数组元素设置为前一个数值；若当前输入数值非正，则该位置对应的数组元素设置为其前一位置数值的相反值。
最后统计数组中第0到第n号元素中数值分别为1和0的数量，并将这两个数量相乘即可得到负区间总数。接着再用总数（计算公式：\frac{n(n-1)}{2}）减去上述得到的结果即可得出正区间的数量。这里进行说明：其中一个是用于确定序列第一个元素是否是正还是负（当该数字不同时），另一个数字则代表扩展范围。具体来说，在这种情况下：如果序列的第一个元素是正，则使用该数字来表示能够被扩展的最大范围；反之，则使用该数字来表示能够被扩展的最大范围。将两者相乘即可得出所有负面区间的总数量。
完整代码：
#include <bits/stdc++.h>
#define int long long
const int maxn=2e5+5;
using namespace std;
int a[maxn],n;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
a[0]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>0){
a[i]=a[i-1];
}
else{
a[i]=1-a[i-1];//因为a[i]的值只有0和1（相当于二进制），1-a[i-1]就是a[i-1]的反（即可实现1变成0，0变成1）（或者^1,x^1=x的反）
}
}
int num1=0,num0=0;
for(int i=0;i<=n;i++)
{
if(a[i]==1){
num1++;
}
else{
num0++;
}
}
int ans1=num1*num0;
int ans2=n*(n+1)/2-ans1;
cout<<ans1<<" "<<ans2<<endl;
return 0;
}