题目链接:http://codeforces.com/contest/1215/problem/B
给你n长度的数组。分别求出任意长度连续区间内乘积为负数和正数的个数。
#include<iostream>
using namespace std;
const int MAXN = 2e5+5;
long long dp1[MAXN], dp2[MAXN]; //以i为结尾的,有dp1[i]个区间含有奇数个负数,dp2[i]个区间含有偶数个负数
long long a[MAXN];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
dp1[1] = (int) (a[1] < 0), dp2[1] = 1-dp1[1];
long long ans1 = dp1[1], ans2 = dp2[1];
for(int i = 2; i <= n; ++i){
if(a[i] < 0){
dp1[i] = dp2[i-1]+1;
dp2[i] = dp1[i-1];
}
else{
dp1[i] = dp1[i-1];
dp2[i] = dp2[i-1]+1;
}
ans1 += dp1[i];
ans2 += dp2[i];
}
cout << ans1 << " " << ans2 << endl;
return 0;
}