增减序列

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

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

输入格式

第一行输入正整数 $n$。

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

输出格式

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

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

数据范围

$1≤n≤10^5$,
$0≤a_i<2147483648$

输入样例

4
1
1
2
2

输出样例

1
2

解析

需要用到知识点 差分数组

有数组 A[1] A[2] A[3] A[4]
差分数组 B[i] = A[i] - A[i - 1]
可得 A[i] = B[1] + B[2] + B[3] + .... + B[i]

含义：原数组 $A_i$ 是差分数组 $B_i$ 的前 $i$ 项和

知道知识点我们来看题

首先需要实现，快速在 $[l,r]$ 区间内进行加减，根据差分数组的定义，在原数组 $A_i$ 的 $[l,r]$ 上作加减 就相当于在差分数组 $B_i$ 的 $B_l$ 与 $B_{r+1}$ 上作加减

比如样例

A_i 1 1 2 2
B_i 1 0 1 0
在[1,2]上 +1，则
A_i 2 2 2 2
B_i 2 0 0 0 (B_1 + 1, B_3 - 1)

好了，已经快速解决 $[l,r]$ 上作加减的问题，就可以来看题目的要求了

① 求最少的操作次数

② 输出最终能得到多少种结果

首先来解决①，我们的目的是 让差分数组除 $B_1$ 外的所有数都变成0，那么我们只需要让差分数组 负的加，正的减 就可以保证每次的选择都是最优选择，这个问题很好解决 一个循环即可。

但每次肯定不会正好减到 0，那我们只需要把多出来全部加到 $B_1$ 就好，这样也满足我们的目的。

然后来解决②，考虑①的最后一步，我们除了将多出来的移到 $B_1$，当然还可以移到 $B_{n+1}$，即将多出来的数再 加一减一 变成0（这里可以理解成在自己[l == r]上操作，也可以理解为在整个差分数组外还有一个规则外的区域），那么只需要多出来几就加上几就好（每个数都有两种选择，加到 $B_1$ 上 或者 不加到 $B_1$ 上）

看代码

#include <cstdio>
#include <iostream>

const int N = 100005;
long long arr[N], g[N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
		g[i] = arr[i] - arr[i - 1]; //差分数组
	}
	
	long long tnt = 0, ans = 0;
	for (int i = 2; i <= n; i++) {
		if(tnt > 0 && g[i] < 0) ans = ans + std::min(tnt, std::abs(g[i])), tnt = tnt + g[i]; 
		else if(tnt < 0 && g[i] > 0) ans = ans + std::min(std::abs(tnt), g[i]), tnt = tnt + g[i]; 
        //异号的情况 说明有正负出现 正的加，负的减就好
		else tnt += g[i]; //同号的情况 那么记录起来就好
	}
	
	printf("%lld\n", ans + std::abs(tnt));
    //最优情况（负的加，正的减   +    多出来的数（可能是负数，记得取绝对值））
	printf("%lld\n", std::abs(tnt) + 1);
    //讨论多少种情况 详细看上面解析
	return 0;
}