9.6字节笔试后端T4题解

https://blog.csdn.net/weixin_41896265/article/details/108435552 这个大佬的代码在这 读了我50min才读懂

首先是把原数组变成期望值-原数组 比如原数组1 2 1 期望全是2 新的数组a就是 1 0 1 建立差分数组(A[I] - A[I-1]) 变成1 -1 1 -1（认为原数组最后结束是0，开始是1）

差分数组d的奇妙的性质就是 在对区间[l,r]+一个值x的时候 除了d[l] = d[l]+x 和 d[r] = d[r]-x之外其他位置都不会发生改变

因此按照题意 任意一个值x顶多开始一次，结束一次区间因此取值只能是1, -1, 0其中0可能代表这一位置没有结束区间或者前一位置结束了但在本位置又新开了一个区间

之后对于得到的差分数组进行遍历 我们在读入的时候已经确保新数组每一位都大于0，并且差分数组要么 是1要么是0要么是-1 因此可以保证任何一个位置之前-1出现的数量一定是小于等于1出现的数量的

首先我们思考一下，对于遇到的1 我们新建一个区间，这个区间左端点已知，右端点未知。对于遇到的0，我们有两种操作，对当前全部区间不进行操作，或者关闭一个当前打开区间，并新建一个以当前位置开头的区间

对于遇到的-1，我们可以从当前打开的区间选择一个进行关闭。

从以上描述我们可以知道，唯一会造成方案数增加的就是遇到0和-1的情况，因为当遇到1时，我们会对当前全部方案添加一个开着的区间，方案数并无变化。而对于-1，我们选择关闭空间的时候可以选择任意当前依然开启的空间，关闭不同的空间得到的方案互不相同。

因此每遇到第i位是-1 进行如下操作 因为在第i-1位时 开放的区间数有a(新数组)[i-1]个 我们随机选择一个关闭 因此会令ans变更为ans*a[i-1]因为差分数组第i位是-1所以a[i] = a[i-1] - 1 所以ans也等于ans*(a[i]+1){最顶上代码就是这么写的 看的时候懵了半天}

如果第i位是0 除了上面说的i-1位关闭区间i位开启空间的情况（这个情况下方案数也是ans*a[i-1]）还有不对区间进行闭合操作的情况 这两种情况的得到的解很显然互不相同 所以ans = ans*(a[i-1]+1)因为差分数组第i位为0所以a[i] = a[i-1]也就是 也能写成ans*(a[i]+1) 也就是上面的代码的写法