Balancing Bacteria (USACO Bronze 2024 January)

从题目规模来看，我们需要 $\mathcal{O}(N)$ 或者 $\mathcal{O}(N\log N)$ 的解：

多次杀虫剂使用之间在会有叠加效应，为了搞清楚具体情况，我们手工做一下例子，比较有意义的是例子2:

第一个1，必须用一个L=5的“负杀虫剂”，才可能清除掉。
我们注意到杀虫剂之间的作用是叠加的，所以对每个位置，我们计算出经过之前的杀虫剂作用之后的值，然后反方向应用同样次数的杀虫剂。
这样不断往右看，我们可以一次扫描得到问题的解。用表格方式，可以这样表达：

   1  3 -2 -7  5  operation      
  -1 -2 -3 -4 -5   -1   <-- 为了解决a[1]，我们使用1次负杀虫剂    
     -1 -2 -3 -4   -1   <-- 为了解决a[2]，我们使用1次负杀虫剂 
         7 14 21    7   <--        a[3]        7次正杀虫剂
            0  0    0   <-- a[4]已经是0
             -17  -17   <--        a[5]        17次负杀虫剂

一共26次杀虫剂使用。

直接用这个2D表格计算，是一个 $\mathcal{O}(N^2)$ 的算法。剩下的问题，是要怎样快速计算这个过程。

我们可以看到以下规律，用来简化计算：

假设v为前面所有已经使用的杀虫剂，对于当前位置的上升或者下降作用。
则每个之前已经使用的正杀虫剂，向右移动一格时，都会带来v++，反过来，每个已经使用的负杀虫剂，向右移动一格时，都会带来v--。所以，我们可以记录“净”的已经使用的正负杀虫剂数量（正负相抵消），为net。则每移动一格时，v+=net.
那对于当前格子，a[i] + v，记为cur，就是我们需要消除的当前格子的差值，如果大于0，则使用负杀虫剂，如果下于0，则使用正杀虫剂。net+=-cur

这样的方法，线性扫描一遍，就得到答案。注意所有数都需要long long。

这是此次比赛中最难的题，程序很短，但是对思维能力要求比较高，杀虫剂作用叠加的部分比较难想。这需要我们不怕困难，不要放弃，都过列出手工计算过程，在这个的帮助下逐渐理清思路，创造出中间变量来完成算法的设计。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;      // 2e5
ll a[200005];
ll ans;
ll net;     // net number of applications in play
ll v;       // cumulative effect from previous applications
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        v += net;
        ll cur = a[i] + v;
        net += -cur;
        ans += abs(cur);
        v += -cur;
    }
    printf("%lld", ans);
 
    return 0;
}