The Number of Products（CF）

这个题几年之前做的时候就是不知道咋做 现在看起来就是一道简单的dp

首先枚举区间肯定是不行的 但是这个题目比较狡猾 数据范围给你2e5 迷惑你不往线性递推方面想

我开始想对每个点分析 分析他对答案会有什么贡献 以往有些题目就是这样的 但是发现没法分析

换个想法 考虑区间[L,R]固定R,依次dp就好

dp[i,0]表示 以i为结尾 结果为负
dp[i,1]表示 以i为结尾 结果为正

转移还是很简单的

a[i]>0
dp[i,1]=dp[i-1,1]+1,dp[i,0]=dp[i-1,0];
a[i]<0
dp[i,0]=dp[i-1,1]+1,dp[i,1]=dp[i-1,0];

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e5+5;
ll n,x,ans1,ans2;
int dp[maxn][2];//1--->正 0---->负 
int main(){
	cin>>n;
	cin>>x;
	if(x<0)dp[1][0]=1,ans1++;
	else dp[1][1]=1,ans2++;
	for(int i=2;i<=n;i++){
		cin>>x;
		if(x<0){
			dp[i][0]=dp[i-1][1]+1;
			dp[i][1]=dp[i-1][0]; 
		}
		else {
			dp[i][1]=dp[i-1][1]+1;
			dp[i][0]=dp[i-1][0];
		}
		ans1+=dp[i][0];
		ans2+=dp[i][1];
	}
	cout<