增减序列（IncDec序列）

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

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

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

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

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

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

数据范围
0< n ≤ 10^5,
0≤ ai <2147483648

输入样例：
4
1
1
2
2

输出样例：
1
2

解析：思路：差分。假如一个序列所有数是相等的，那么差分之后可能只有delt[1] != 0，其他的必为0，那最少的操作次数肯定是差分数组中的正数与负数比较后最大的那个，因为每次只能加一或减一，可以拿一个例子来解释，比如现在的序列是：3 2 2 3，这里一眼可以看出最少只用操作一次，就是把l = 2，r = 3的区间进行+1就全部变为3，实际上此时的差分数组是delt[1] = 3,delt[2] = -1, delt[3] = 0,delt[4] = 1，那其实我们可以利用差分的性质，在l = 2的数组+1，那在r = 4的数组-1就都变为0，而实际上操作的区间是[2,3]，这个解释是在了解差分原理后进行解析的。所有差分数组中正负抵消后就看还剩下正的差分数组还是负的。不过这道题还需要求出最少的操作有多少种结果，答案是：abs(差分数组中的正数和 - 差分数组中的负数和) + 1，这我真的想不到，不过看了题解后，我是这样理解的：拿样例来说，它的差分数组是1，0，1，0，那显然最少只用操作一次就可以了，接下来差分数组的正数和（不看第一个差分数组，因为第一个不影响）是1，然后假如我们让l = 1加上1，r = 3减去1，那此时差分数组就是2，0，0，0，得到的序列是（2，2，2，2），假如我在l = 3减去1，而在r = 无穷大的数加上1，那现在差分数组就是1，0，0，0，得到的序列是（1，1，1，1），挺有意思的~可以多找几个例子，你就能发现其中的奥秘！

AC代码：

#include<bits/stdc++.h>
typedef long long LL;
const int maxn = 1e5 + 7;
LL a[maxn], delt[maxn];
LL n, pos, neg;

int main()
{
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		delt[i] = a[i] - a[i-1];
	}
	for(int i = 2; i <= n; i++)
	{
		if(delt[i] >= 0)
			pos += delt[i];
		else
			neg -= delt[i];
	}
	printf("%lld\n%lld", std::max(pos, neg), abs(pos - neg) + 1);
	return 0;
}

本来这周的训练是差分的，不过这周找的题目翻车了，只有几道是差分的题，其他的用到其他的知识点去了，然后剩下的差分比较easy，就没写题解了，期末周了，要好好复习嗷

增减序列（IncDec序列）

原文：https://www.cnblogs.com/K2MnO4/p/13132273.html