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

题目

代码

#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;
}