【最优清零方案——贪心+滑动窗口+线段树】

题目

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int a[N];
struct node
{
    int l, r;
    int m, p, lazy;
} tr[4 * N];
void pushup(node &u, node &l, node &r)
{
    if (l.m == r.m)
    {
        u.m = l.m;
        u.p = max(l.p, r.p);
    }
    else if (l.m < r.m)
    {
        u.m = l.m;
        u.p = l.p;
    }
    else
    {
        u.m = r.m;
        u.p = r.p;
    }
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(node &u, node &l, node &r)
{
    if (u.lazy)
    {
        l.m = max(l.m + u.lazy, 0);
        r.m = max(r.m + u.lazy, 0);
        l.lazy += u.lazy;
        r.lazy += u.lazy;
        u.lazy = 0;
    }
}
void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {l, r, a[l], l};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int d)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].lazy += d;
        tr[u].m = max(tr[u].m + d, 0);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, d);
    if (r > mid)
        modify(u << 1 | 1, l, r, d);
    pushup(u);
}
node query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u];

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
        return query(u << 1, l, r);
    else if (l > mid)
        return query(u << 1 | 1, l, r);
    else
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        node ans;
        pushup(ans, left, right);
        return ans;
    }
}
int main()
{
    int n, k;
    cin >> n >> k;

    ll sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    build(1, 1, n);

    int l = 1, r;
    ll cnt = 0;
    while (r = l + k - 1, r <= n)
    {
        auto u = query(1, l, r);
        int minn = u.m;
        cnt += minn;
        modify(1, l, r, -minn);
        l = u.p + 1;
    }

    cout << sum - k * cnt + cnt;
}