先看题目，因为在文中可以发现，它有一个区间加区间减的操作，所以我们想到了线段树和差分，而下面题目是要我们自己查找让所有的数字相同的最小步数。
因此我们可以将线段树排除，那么来看差分，对于差分而言，所有的数字都相同，就可以看作对于所有的 $2\le i \le n$ 而言，$a_i = 0$，最后的结果是所有的数都与 $a_1$ 一样。
先来看第一问，最少步数。那么对于差分数组来说，每一次的区间操作可以让两个位置的值发生改变，那么能让两个改变位置都在 2~n 中自然是最快的，所以我们令 p为所有正数的绝对值之和，q为所有负数的绝对值之和 那么能让左右端点变化都在范围内的步数是 $min(p,q)$，只有一个端点的步数是 $abs(p-q)$。所有第一问的答案就是 $max(p,q)$。
第一问解决之后来看第二问，前文说过最后的数列全都是 $a_1$ 的值。所以最终的种类数就是 $a_1$ 值的种类数。因为要最少步数达到，所以每个两端点贡献的操作左右端点固定。那么所有一个端点的操作数就是所有可以改变 $a_1$ 值的操作数，所以数量为一步操作数加一（因为原来也有个值）。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000 + 5;
int a[N];
int n;
long long s1, s2;
int main() {
scanf ("%d", &n);
for (int i = 1;i <= n; ++ i)
scanf ("%d", a + i);
for (int i = n;i > 1; -- i)
a[i] -= a[i - 1];
for (int i = 2;i <= n; ++ i) {
if (a[i] > 0) s1 += a[i];
else s2 -= a[i];
}
printf ("%lld\n", max (s1, s2));
printf ("%lld\n", abs (s1 - s2) + 1);
return 0;
}
完结撒花
标签：int,s2,s1,所有,P4552,端点,Poetize6,IncDec,步数 From： https://www.cnblogs.com/Assassins-Creed/p/18018376