和与乘积---详细注释

解题思路:
见代码详细注释

参考代码:

#include<bits/stdc++.h>
#define endl "\n"
typedef long long ll  ;
using namespace std;
const int N = 2e5+10;
//sum数组记录前缀和数组 a数组为原始数据数组 b为a中值不为1的元素所构成的数组
//id[i]表示在b数组中下标为i的元素原始下标即在a数组中的下标  -- 用于前缀和计算
//l1 表示在a中的元素最左边的1的下标 同理 r1表示在a中的元素最右边的1的下标
//例如:1 2 2 3 2 1  其中 l1[2] = 1 r1[2] = 0;l1[5] = 0,r1[5] =  6;
//得到这个下标就可以进一步计算出某元素的相邻左边 有几个1 相邻右边有几个1 
int sum[N],a[N],b[N],l1[N],r1[N];
int ans = 0,id[N],blen;
int n;
void solve() {
	cin>>n;
	ans += n;//ans 先加上元素个数 每个元素可以单独作为一种答案 
	for(int i = 1;i<=n;i++){//计算前缀和 
		cin>>a[i];
		sum[i] = sum[i-1] + a[i]; 
		if(a[i]!=1){//把不为1的元素放到b数组中去 
			b[++blen] = a[i];
			id[blen] = i;//记录原始的下标 
		}
	}
	//预处理l1 r1 
	int dex1 = 0,dex2 = 0;
	for(int i = 1,j = n;i<=n;i++,j--){
		if(a[i] == 1&&!dex1) {//当a[i]==1 且 处于目前这块区域最左边的 比如 1 1 2 中2记录的l1应该是1而不是2 
			dex1 = i;
		}else if(a[i]!=1){
		//a[i]!=1 需要给他l1的值 同时此区域的最左1寻找结束 把dex1 = 0 
		//例如1 2 3 中1的记录在赋值给2的l1后就结束  3不会拿到上一区域的记录 2隔断了 就是说3的左边区域是没有1的 
			l1[i] = dex1;
			dex1 = 0;
		}
		if(a[j] == 1&&!dex2){//r1的处理同上 
			dex2 = j;
		}else if(a[j]!=1){
			r1[j] = dex2;
			dex2 = 0;
		}
	}
	//选取区间  这个区间是从 b 里面取出不为1的元素作为左边起点和右边界限点 
	//一个区间要满足条件 必须要 相邻左右边的 1 来凑 1加入该区域 他的和+1 而乘积不变 这样才有机会满足条件 
	for(int i = 1;i<=blen;i++){//左边起点 
		ll multi = b[i];
		dex1 = id[i];//左起点的原始下标 
		for(int j = i+1;j<=blen;j++){//右边界限点 
			multi *= b[j];//记录乘积 
			if(multi > sum[n]) break;//如果当前区域的乘积大于最大和(所有元素之和)
			//再后移右边界区域更大就肯定不会有成立的情况 
			dex2 = id[j];//右起点的原始下标 
			ll dis = multi - (sum[dex2] - sum[dex1-1]);//要该区域成立 所需要 1 的个数 
			if(dis == 0) {//不需要1了直接ans++ 即该区间已经满足条件 例如 2 2 
				ans++ ;
				continue;
			}
			ll x = dex1 - l1[dex1];//得到该区域左边有几个相邻的 1 
			if(l1[dex1]==0) x = 0;//前面提到当 l1[dex1]==0 表示的是dex1的左边没有1 要对x进行修改 
			x = min(x,dis);//我左边相邻有5个 1 但可能只需要 3 个1 取两者的最小值作为左边能够加入该区域的 1的个数 
			ll y = r1[dex2] - dex2;//同上得到右边的情况 
			if(y<0) y = 0;//r1[dex2]==0特殊情况重置 
			y = min(y,dis);
			if(x + y < dis) continue;//两边能够加入区域的总个数小于 dis 条件不可能成立 例如我有3个1 但需要5个1 
			else{
				ans +=1 +  (x + y) - dis;//条件符合时的情况数 
				//例如 1 1 2 3 1 1 我可以选左边的2号1 也可以选右边的5号1 
				// + 1是指此时我有的相邻1数目大于需要的数目 就一定存在成立的情况 先选取把最左边的1加入区域的情况 
				//即先+1 此时可以通过窗口移动来更换左右两边加入的1  
				//例如 1 1 1 2 3 1 1 先选取3号位的1加入2 3区域 再移动一步把右边的6号位加入该区域 这是不同的情况
				//再例如 我需要4个1  假如左 右边都相邻的4个1 我先选最左边的4个1加入 再移动 左边选3个右边选1个 
				//再移动左边2个 右边2个...
				//通过移动的方式所增加的方案数为 x+y - dis 
			}
		}	
	}
	cout<<ans;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}