AcWing 3574. 乘积数量
原题链接
中等
//暴力法:
#include<iostream>
using namespace std;
int n,a[200005],sum[200005],ans,res;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x>0) a[i]=1;
else a[i]=-1;
}
sum[0]=1;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]*a[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(sum[j]/sum[i-1]>0) ans++;
else res++;
}
}
cout<<res<<" "<<ans<<endl;
return 0;
}
//优化
#include<iostream>
#define int long long
using namespace std;
int n,a[200005],sum[200005],id_z=1,id_f=0;
int C(int n,int k){
if(k==2) return n*(n-1)/2;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x>0) a[i]=1;
else a[i]=-1;
}
sum[0]=1;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]*a[i];
for(int i=1;i<=n;i++){
if(sum[i]>0) id_z++;
else id_f++;
}
cout<<id_z*id_f<<" "<<C(id_z,2)+C(id_f,2)<<endl;
return 0;
}