[Acwing] 100. 增减序列 差分

前言

好难的一题 传送门 :

前言

对于差分操作,如果一个区间加上一个常数c: 如下 d [ l ] + = c     ,     d [ r ] − = c     ( d 为 差 分 数 组 ) d[l]+=c\ \ \ , \ \ \ d[r]-=c \ \ \ (d为差分数组) d[l]+=c   ,   d[r]−=c   (d为差分数组)

如果一个数组所有数都一样也就是说明差分数组为0

又因为 : b [ 1 ] = a [ 1 ] , b [ 2 ] = a [ 2 ] − a [ 1 ] , b [ 3 ] = a [ 3 ] − a [ 2 ] . . . . . b[1] = a[1],b[2]=a[2]-a[1],b[3]=a[3]-a[2]..... b[1]=a[1],b[2]=a[2]−a[1],b[3]=a[3]−a[2].....

因此这个题目可以转换为, 从 [ 2 − n ] [2-n] [2−n]选出两个数,一个 + 1 +1 +1,一个 − 1 -1 −1,使得 b [ 2.. n ] = 0 b[2..n] = 0 b[2..n]=0

这样子数组就变为了 n n n个 a [ 1 ] a[1] a[1] , 这样子显然的我们尽可能需选出 b [ l ] ∗ b [ r ] < 0 b[l]*b[r]