AcWing 3574. 乘积数量
原题链接
中等
作者:
陈平安
,
2021-05-26 21:32:49
,
所有人可见
,
阅读 517
方法:前缀和(或许前缀积?)
/*
做题的时候有思路,就是代码实现的时候有一个小细节错误。
首先,这道题是关于连续区间的,那么可以转化为前缀和。
因为只统计正数、负数的个数,所以并不需要存真正的数,只需要存一下正负即可。
(这里采用小技巧,当输入的数>0,置成+1,当输入的数<0,置成-1,这样算前缀积的时候就不会爆long long了)
声明,a数组表示原数组,s数组表示前缀积数组。
定义两个数组:b数组,c数组
b[i]状态表示: s[1]~s[i]中正数的个数
b数组状态计算: if(s[i]>0) b[i]=b[i-1]+1;
else b[i]=b[i-1];
c[i]状态表示: s[1]~s[i]中负数的个数
c数组状态计算:if(s[i]<0) c[i]=c[i-1]+1;
else c[i]=c[i-1];
前缀积可以类比前缀和求出,但要初始化s[0]=1,不然全部都是0,就不正确了。(当然,也可以从第二项开始算前缀积)。
现在算正的索引对
现在扫描前缀积s,当s[i]>0,我们要找以从1到1~s[i]的正数的前缀区间个数,即b[i],则res+=b[i];
为什么这样找呢,因为s[i]/s[j]表示j+1~i这个连续区间的乘积(1=<j<=i)采用这种方式可以找遍所有以第i个数结尾的连续区间,下面同理
当s[i]<0,我们要找以从1到1~s[i-1]的负数的前缀区间个数,即c[i-1],则res+=c[i-1];
这里为什么不能找s[i]呢,因为s[i]是负,则s[i]~s[i]为s[i]为负,不满足要求。所以从前一项找起。
现在我们知道了正的索引对,因为连续区间个数是(n+1)*n/2 (以每个点为起点的区间个数是一个等差数列,利用公式求和可以求出连续区间总数)
那我们减一下就可以求出负的索引对了。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200010;
ll res;
int a[N];
int s[N];
int b[N];
int c[N];
int n;
int main()
{
scanf("%d",&n);
s[0]=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>0) a[i]=1;
else a[i]=-1;
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]*a[i];
}
for(int i=1;i<=n;i++)
{
if(s[i]>0) b[i]=b[i-1]+1;
else b[i]=b[i-1];
if(s[i]<0) c[i]=c[i-1]+1;
else c[i]=c[i-1];
}
for(int i=1;i<=n;i++)
{
if(s[i]>0) res+=b[i];
else res+=c[i-1];
}
printf("%lld %lld",(ll)n*(n+1)/2-res,res);
return 0;
}