The Number of Products
发布时间
阅读量：
阅读量
给定一个序列a1，a2，…，由n个非零整数组成（即ai≠0）。
请计算以下两个值：
指数对（l，r）（l≤r）的数目，使得al⋅al+1…ar−1⋅ar为负；
指数对（l，r）（l≤r）的数目，使得al⋅al+1…ar−1⋅ar为正；
The first line contains one integer n (1≤n≤2⋅105) — the number of elements in the sequence.
The second line contains n integers a1,a2,…,an (−109≤ai≤109;ai≠0) — the elements of the sequence.
Output
Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively.
Examples
Input
5
5 -3 3 -1 1
Output
8 7
Input
10
4 2 -4 3 1 2 -4 3 2 3
Output
28 27
Input
5
-1 -2 -3 -4 -5
Output
9 6
分析：先考虑全部为正的序列，则正积段为n+(n-1)+…+1种取法，所以正负积段总和为n * (n + 1) / 2,求出正积段即可求出负积段
在此基础上，我们只考虑正负，不考虑乘积的结果，所以令正数为0负数为1，用前缀和统计奇偶，维护两个桶前缀和分别为奇数和偶数的个数，
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
int a[maxn], sum[maxn], cnt[2];
long long pos, neg;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
if(a[i]>0) a[i]=0;
else a[i]=1;
}
for(int i=1; i<=n; i++)
sum[i]=sum[i-1]+a[i];
for(int i=1; i<=n; i++)
sum[i]=sum[i]%2;
cnt[0]++; //注意cnt0初始化为1，表示区间长度为1的那个
for(int i=1; i<=n; i++)
{
if(sum[i]){
pos+=cnt[1];
}
else{
pos+=cnt[0];
}
cnt[sum[i]]++;
}
long long k = n * (n + 1) / 2;
cout<<k - pos <<" "<<pos;
return 0;
}
cpp
全部评论 (0)
还没有任何评论哟~