在BZOJ上好像被权限掉了。
考虑差分，定义差分数组$b$
$$b_i = \left\{\begin{matrix}
a_i \ \ \ (i == 1)\\
a_i - a_{i - 1}\ \ \ (i > 1)
\end{matrix}\right.$$
那么我们最后就是要使 $\forall i \in [2, n]\ \ b_i == 0$，并不关心$b_1$的取值。
差分之后区间修改变成了$+1$和$-1$的单点修改，如果要用最少的次数完成修改，那么肯定先要对所有$b_i > 0$的进行$-1$的操作，而$b_i < 0$得进行$+1$的操作，发现正负数可以两两配对，设$b_i$ $i \in [2, n]$中所有正数的和为$p$，所有负数的绝对值和为$q$，那么有$min(p, q)$次可以配对修改，还有$\left | p - q \right |$需要拎出来单独修改，那么第一问的答案就是$min(p, q) + \left | p - q \right | = max(p, q)$。
而第二问相当于求有多少个$b_1$，易得答案为$\left | p - q \right | + 1$。
时间复杂度$O(n)$。
注意开$long \ long$。
Code：
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 1e5 + 5; int n; ll a[N], b[N], sumP = 0, sumN = 0; template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > ‘9‘|| ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) op = -1; for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } template <typename T> inline T max(T x, T y) { return x > y ? x : y; } template <typename T> inline T abs(T x) { return x > 0 ? x : -x; } int main() { read(n); for(int i = 1; i <= n; i++) { read(a[i]); b[i] = a[i] - a[i - 1]; if(i == 1) continue; if(b[i] < 0) sumN -= b[i]; if(b[i] > 0) sumP += b[i]; } printf("%lld\n%lld\n", max(sumN, sumP), abs(sumP - sumN) + 1LL); return 0; }
Luogu 4552 [Poetize6] IncDec Sequence
原文：https://www.cnblogs.com/CzxingcHen/p/9738754.html
