差分_牛客博客

给定一个长度为 $n (n \leq 1 0^{5})$ 的数列 $a_{1}, a_{2}, \dots, a_{n}$ ，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
先差分， $d_{1} = a_{1}, d_{n + 1} = - a_{n + 1}$ 相当于每次取两个数，一个加一，一个减一，最后使得 $d_{2} = d_{3} = \dots = d_{n} = 0$
有下面四种操作：

$d_{i}, d_{j}$ 加减1，其中2<=i,j<=n
$d_{i}, d_{n + 1}$ 加减1,其中2<=i<=n
$d_{n + 1}, d_{j}$ 加减1，其中2<=j<=n
$d_{1}, d_{n + 1}$ 加减1

4操作没用，为了次数最少，优先操作1，操作完了之后， $d_{i}$ >=0或 $d_{i}$ <=0
1操作完了之后，只能操作2/3，且操作次数为剩余的不为0的数的绝对值的和