##[$AcWing$ $100$. 增减序列](https://www.acwing.com/problem/content/102/)

### 一、题目描述
给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能 **使数列中的所有数都一样**，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

**输入格式**
第一行输入正整数 $n$。

接下来 $n$ 行，每行输入一个整数，第 $i+1$ 行的整数代表 $a_i$。

**输出格式**

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

**数据范围**
$0<n≤10^5,0≤a_i<2147483648$

**输入样例**：
```cpp {.line-numbers}
4
1
1
2
2
```
**输出样例**：
```cpp {.line-numbers}
1
2
```

### 二、题目解析

#### 差分复习

对于一个给定序列 $a$, 它的差分序列 $b$ 定义为：
$$  b[1]=a[1] ① \\  b[i]=a[i]−a[i−1]  (2≤i≤n)②$$

可以发现， **前缀和** 、 **差分** 是一对互逆运算，$b$ 序列的前缀和就是 $a$ 序列。

**应用**
如果要把序列 $a$ 的 $[l,r]$ 区间内的所有数加 $d$，差分序列 $b$ 的变化为 $b[l]$ 加 $d$，$b[r+1]$ 减 $d$,减法同理。

#### 本题思路
因为题目中提到在原数组 $a[i]$的某个区间上要么加$1$，要么减$1$,也就是一维数组的区间加减问题，符合 **差分** 的应用场景,使用差分，可以使得原来$r-l+1$次修改变成$2$次，可以节约大量的计算时间，所以，本题应该考虑使用差分。

那我们就需要求出 $a$ 的差分序列 $b$。

题目的最终目标是把数组的全部数字变成一样的，那么，对应到差分数组，就是
$b[1],b[n+1]$是什么值都可以，但$b[2],b[3],...b[n]$都需要等于$0$，并且，$b[1]$的值就是最终数组$a[]$的所有数字一样的那个值。

**以数据样例为例进行理解**
```cpp {.line-numbers}
原始数组：    1 1 2 2
差分数组:     1 0 1 0
```
- $A$方案，前两个$+1$:``` 2 2 2 2 ```
差分数组随之变化,$1$位加$1$，$2+1=3$位减$1$,得到如下的差分数组：
```cpp {.line-numbers}
2 0 0 0
```

- $B$方案，后两个$-1$:``` 1 1 1 1 ```
差分数组随之变化,$3$位减$1$，$4+1=5$位加$1$,得到如下的差分数组：
```cpp {.line-numbers}
1 0 0 0 1
```
**咦？为什么原数组是$4$个数字，你的差分是$5$个数字呢?**

你看一下上面的应用$a[l-r]$加上$d$,是不是$b[l]+=d,b[r+1]-=d$,而$1<=l<=r<=n$
考虑一下边界问题，如果 $r=n$时，上面的
$$b[r+1]-=d \Rightarrow b[n+1]-=d $$
也就是说，$b[]$数组需要考虑到$n+1$项，此时，如果$r=n$时，也就是变化区间最右边到$n$时，就用到了$b[n+1]$,但$b[n+1]$最终是什么值不重要，它的值不影响区间内所有元素的值一样。

**贪心思路求变化最小次数**

> **转化**：题目对 $a$ 序列的 **任何区间加减$1$操作**，等同于对 $b$ 序列中的 **任意两数**，一个加 $1$，一个减 $1$。
> **目标** : 把 $b[2]$ 至 $b[n]$ 全变为 $0$,$b[1],b[n+1]$是多少无所谓。

从 $b[1]$ 至 $b[n+1]$ 中 **任选** 两数的方案进行分类讨论：

由于$b[1],b[n+1]$比较特殊，所以划分分类时，以它们为分类标准进行划分四类：

- **① 选 $b[i]$ 和 $b[j]$**
  其中 $2≤i,j≤n$，这种操作会改变 $b[2]$ 至 $b[n]$ 中两个数的值，因为差分操作，无外乎就是：
  - 前项$+1$，后项$-1$
  - 前项$-1$，后项$+1$
  这两种情况，目标是把这段区间所有数字变成$0$,那大于$0$的得$-1$向小了变，小于$0$的得$+1$向大的变。也就是尽量挑 $b[i]$ 和 $b[j]$ **一正一负** 的情况下，这样一下就可以 **变掉两个数**，使得整体向都是$0$的区间逼近。

- **② 选 $b[1]$ 和 $b[j]$**
  其中 $2≤j≤n$；这种情况下也是两种可能分支:
  - $b[j]>0$,那么$b[j]-=1$,$b[1]+=1$
  - $b[j]<0$,那么$b[j]+=1$,$b[1]-=1$
   因为我们并不关心$b[1]$的最终值是多少，只关心尽快的把b[2 \sim n]变成$0$,所以，这样一下只能改一个数字，效率不如上面的 ① 快。

- **③ 选 $b[i]$ 和 $b[n+1]$**
  其中 $2≤j≤n$；这种情况下也是两种可能分支:
  - $b[i]>0$,那么$b[i]-=1$,$b[n+1]+=1$
  - $b[i]<0$,那么$b[i]+=1$,$b[n+1]-=1$
   因为我们并不关心$b[n+1]$的最终值是多少，只关心尽快的把$b[2 \sim n]$变成$0$,所以，这样一下只能改一个数字，效率不如上面的 ① 快。

- **④ 选 $b[1]$ 和 $b[n+1]$**
  因为它不会改变 $b[2]$ 至 $b[n]$ 的值，浪费了操作，一定不是最优解,放弃这种可能。

所以，我们的贪心策略就是：尽量的采用方法 ①,如果实在没有办法使用方法 ①时，再考虑使用方法 ② 或者 方法 ③。

那什么情况下可以使用方法 ① 呢？ 限制条件是在$b[2 \sim n]$中存在$1$个及$1$个以上大于$0$的数字，并且，存在$1$个及$1$个以上小于$0$的数字，才能进行此操作。

所以，有了如下的神操作：

**设 $b[2]$ 至 $b[n]$ 中正数总和为 $p$，负数总和的绝对值为 $q$。**

首先，我们以正负配对的方式执行操作，可执行 $min(p,q)$ 次，剩余 $|p−q|$ 个没有配对。

接下来，剩下的每个与 $b[1]$ 或 $b[n+1]$ 配对，共需 $|p−q|$ 次。


**综上**，最少操作次数为 $min(p,q)+|p−q|=max(p,q)$ 次。

下面来思考第二个问题：
> **保证最少次数的前提下，最终得到的数列可能有多少种?**

答：在尽量采用方法 ① 的情况下，可以尽快的使得整体区间向全是$0$进行逼近，但最后，随着正数或者负数的消亡，剩下了$|p-q|$个正数值或者负数值，此时，只能通过与$b[1]$或 $b[n+1]$的 **捉对** 操作才能完成整体全是$0$的目标

假设剩下$|p-q|$个：
  - $b[1]$消耗掉$0$个，$|p-q|$个交给$b[n+1]$消耗掉
  - $b[1]$消耗掉$1$个，$|p-q|-1$个交给$b[n+1]$消耗掉
  - $b[1]$消耗掉$2$个，$|p-q|-2$个交给$b[n+1]$消耗掉
  ...
  - $b[1]$消耗掉$|p-q|$个，$0$个交给$b[n+1]$消耗掉
  - 共有$|p-q|+1$种情况，此时，$b[1]$的值也随之变化，共$|p-q|+1$种结果。
  


### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int a[N], b[N];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }

    LL p = 0, q = 0;
    for (int i = 2; i <= n; i++)
        if (b[i] > 0)
            p += b[i];
        else
            q -= b[i];

    printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
    return 0;
}
```