D.统计子区间乘积 -- dp

 1 

#include 
 2 using std::cin;
 3 using std::cout;
 4 using i64 = long long;
 5 const int N = 1e5 + 7;
 6 int a[N];
 7 int dp[N],ep[N];
 8 int main(){
 9     std::ios::sync_with_stdio(false);
10     std::cin.tie(nullptr);
11     int n;
12     cin >> n;
13     long long zero = 0,fu = 0,zheng = 0;
14     for(int i = 1; i <= n;i++){
15         cin >> a[i];
16     }
17     for(int i = 1; i <= n; i++){
18         if(a[i] > 0){
19             dp[i] = dp[i - 1] + 1;
20             ep[i] = ep[i - 1];
21             zheng += dp[i],fu += ep[i];
22         }else if(a[i] < 0){
23             dp[i] = ep[i - 1];
24             ep[i] = dp[i - 1] + 1;
25             zheng += dp[i],fu += ep[i];
26         }else{
27             dp[i] = ep[i] = 0;
28         }
29         
30     }
31     zero += (n * 1ll * (n + 1) / 2 - zheng - fu);
32     cout << fu << " " << zero << " " << zheng <<"\n";
33     return 0;
34 }