• 方法一： 二阶差分

在差分两次后的数组的 $i$ 位置上加 1，就等价于在原数组 $i$ 至 $n$ 上加了一个首项为 $1$ 公差为 $1$ 的等差数列。

所以，数组 $a$ 两次差分后所有数的绝对值的和，即为将原数列应加上等差数列的个数。

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll n, a[N], s[N], s2[N], ans;
int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = a[i] - a[i-1];
        s2[i] = s[i] - s[i-1];
        ans += abs(s2[i]);
    }
    cout << ans;
    return 0;
}

• 方法二：模拟优化

从左往右计算每一个位置需要几次除菌，维护并计算出在位置 $n$ 的总的贡献以及贡献次数。

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
   
    int n; cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
   
    ll ans = 0;
    ll contribution = 0;
    ll cnt_ops = 0;
    for (int i = 0; i < n; i++) {
        contribution += cnt_ops;
        a[i] += contribution;
        
        ll cur_ops = -a[i];
        ans += abs(cur_ops);
        cnt_ops += cur_ops;
        contribution += cur_ops;
    }
    
    cout << ans << '\n';
}