P10133 [USACO24JAN] Balancing Bacteria 题解

yyrwlj · 2024-02-05 22:06:03 · 题解

思路

首先发现操作的先后次序是无所谓的，那么我们就可以从左往右修复，修复了之后就不要再喷它了。

那么每次操作必须保证喷到当前草地时，恰好只会去除 1 或 -1 单位的细菌，然后操作当前草地的当前细菌水平的绝对值次。

我们发现这对于从当前草地到第 n 个草地到影响是一个等差数列，然后每次看当前草地的细菌水平是一个单点查询。

那么我们可以用一个支持区间加等差数列，单点查询的线段树，发现这是原，让原序列转成差分序列后，就方便用区间和线段树维护了。

Code

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200005;
LL a[N], w[N << 2], tag[N << 2];
int n;
inline void pushup(int u)
{
    w[u] = w[u << 1] + w[u << 1 | 1];
}
void build(int u,int l,int r)
{
    if (l == r)
    {
        w[u] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
inline void pushdown(int u,int l,int r,int mid)
{
    tag[u << 1] += tag[u];
    tag[u << 1 | 1] += tag[u];
    w[u << 1] += tag[u] * (mid - l + 1);
    w[u << 1 | 1] += tag[u] * (r - mid);
    tag[u] = 0;
}
void update(int u,int l,int r,int L,int R,LL x)
{
    if (L <= l && r <= R)
    {
        tag[u] += x;
        w[u] += (r - l + 1) * x;
        return;
    }
    int mid = (l + r) >> 1;
    if (tag[u])
        pushdown(u, l, r, mid);
    if (L <= mid)
        update(u << 1, l, mid, L, R, x);
    if (mid < R)
        update(u << 1 | 1, mid + 1, r, L, R, x);
    pushup(u);
}
LL query(int u,int l,int r,int L,int R)
{
    if (L <= l && r <= R)
        return w[u];
    int mid = (l + r) >> 1, res = 0;
    if (tag[u])
        pushdown(u, l, r, mid);
    if (L <= mid)
        res += query(u << 1, l, mid, L, R);
    if (mid < R)
        res += query(u << 1 | 1, mid + 1, r, L, R);
    return res;
}
inline void change(int l,int r,int k,int d)
{
    update(1, 1, n, l, l, k);
    if (l < r)
        update(1, 1, n, l + 1, r, d);
}
inline LL ask(int p)
{
    return query(1, 1, n, 1, p);
}
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%lld", &a[i]);
    for(int i=n-1;i;i--)
        a[i + 1] -= a[i];
    build(1, 1, n);
    LL ans = 0;
    for (int i=1;i<=n;i++)
    {
        const LL ai = ask(i);
        if (ai < 0)
            ans -= ai;
        else
            ans += ai;
        change(i + 1, n, (-ai) * 2, -ai);
    }
    printf("%lld", ans);
    return 0;
}